$$ \sum (a _ i - b _ i) ^ 2 = \sum (a _ i ^ 2 + b _ i ^ 2) - 2\sum a _ i b _ i $$ 即需要考虑最大化 $\sum a _ i b _ i$ 。考虑两个序列升序序列 $a _ 1, a _ 2, \ldots, a _ n$ 和 $b _ 1, b _ 2, \ldots, b _ n$ ,若交换 $i, j$ ,贡献变化为: $$ a _ i b _ j + a _ j b _ i - a _ i b _ i - a _ j b _ j = (a _ i - a _ j) (b _ j - b _ i) $$ $a _ i - a _ j$ 和 $b _ j - b _ i$ 中必有一个负数,故贡献减少。故可以归纳证明,满足答案的序列需要满足第 $k$ 大的 $a$ 与第 $k$ 大的 $b$ 需要交换在一起。
#include<cstdio> #include<vector> #include<algorithm> usingnamespace std; template <classType> voidread(Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') c == '-' && (flag = true); x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0'; flag && (x = ~x + 1); } template <classType> voidwrite(Type x) { x < 0 && (putchar('-'), x = ~x + 1); x > 9 && (write(x / 10), 0); putchar(x % 10 + '0'); } constint N = 1e5 + 10, mod = 1e8 - 3; int tr[N]; int n, u[N], v[N], w[N]; voidDiscretization(int n, int *x) { vector<int> ws; for (int i = 0; i < n; i++) ws.push_back(x[i]); sort(ws.begin(), ws.end()); staticint tmp[N]; for (int i = 0; i < n; i++) tmp[i] = x[i]; for (int i = 0; i < n; i++) x[lower_bound(ws.begin(), ws.end(), tmp[i]) - ws.begin()] = i + 1; } voidmodify(int x) { for (; x <= n; x += x & -x) tr[x]++; } intquery(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res; } intmain() { read(n); for (int i = 0; i < n; i++) read(u[i]); for (int i = 0; i < n; i++) read(v[i]); Discretization(n, u), Discretization(n, v); for (int i = 0; i < n; i++) w[u[i]] = v[i]; int res = 0; for (int i = n; i; i--) { (res += query(w[i])) %= mod; modify(w[i]); } write(res); return0; }