给定两个数列 a,b a, b ，每个数列中相邻两个数可以交换，求使得 ∑i=1n(ai−bi)2 \sum\limits_{i = 1}^{n}(a_i - b_i) ^ 2 最小的交换次数，答案对 99999997 99999997 取模

题解

当∣a−b∣|a-b|尽可能小的时候，(a−b)2(a-b)^2最小，所以，这道题实际上就是让数列aa中的元素与数列bb中的元素，按照它们在两个数列中所在的大小位置对应排列，简单来说，比如某个元素aja_j在数列aa中是第三大的，那么满足题意的与他对应的bjb_j在数列bb中也一定是第三大的。详细的证明过程不再赘述（其实是我自己证明困难QwQ）

具体做法就是现将两个数列排序，这样我们就获得了两个数列中哪两个元素应该对应排列在一起，然而实际操作并不需要同时移动两列数，我们只需要固定一列数移动另一列使其满足该大小关系即可，所以我们记录每个元素本来的位置，问题转化为求一个序列中原位置关于另一个序列原位置的逆序对。。确实很绕，上代码理解吧。。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
const int MOD = 99999997;
struct Stick {
    int id, height;
    bool operator<(const Stick &other) const { return height < other.height; }
} s1[MAXN + 1], s2[MAXN + 1];
int t[MAXN + 1], tmp[MAXN + 1];
int ans;
void mergeSort (int *a, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] > a[j]) {
            tmp[k++] = a[j++];
            ans = (ans + (mid - i + 1) % MOD) % MOD;
        } else {
            tmp[k++] = a[i++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = tmp[i];
    return;
}
int main () {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) { scanf("%d", &s1[i].height); s1[i].id = i; }
    for (int i = 0; i < n; i++) { scanf("%d", &s2[i].height); s2[i].id = i; }
    sort(s1, s1 + n);
    sort(s2, s2 + n);
    for (int i = 0; i < n; i++) t[s2[i].id] = s1[i].id;
    mergeSort(t, 0, n - 1);
    printf("%d\n", ans);
    return 0;
}