思路
首先可以口胡证明，当 \(A\) 数组和 \(B\) 数组均为升序排列时，\(\sum\limits_{i=1}^n (a_i-b_i)^2\) 最小。
但在这道题中，我们只需要让在升序排列中，两数组中下标相同的数对应即可。
以样例中 \(A,B\) 数组为例，将它们分别离散后列出：
\(A: 2 \ \ 3 \ \ 1 \ \ 4\)
\(B: 3 \ \ 2 \ \ 1 \ \ 4\)
根据上述结论，当 \(A_i = x\) 时，\(B_i\) 也应该等于 \(x\)。
也就是说，如果建立一个数组 \(C\)，令 \(C_{A_i}=B_i\) 的话，应该满足 \(C_i=i\)。
但在样例中，可以列出 \(C\) 数组：
\(C: 1 \ \ 3 \ \ 2 \ \ 4\)
我们的目标是让 \(C\) 数组升序排列，而每次交换最多消除一个逆序对。
故题目的答案就是 \(C\) 数组的逆序对数。
求逆序对可以用树状数组或归并排序，代码中使用的是归并排序。
时间复杂度 \(O(N\log N)\)
CODE
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
int x,id;
node() {
x = id = 0;
}
node(int x,int id):x(x),id(id){}
bool operator < (const node& p)const {
return x < p.x;
}
}a[maxn],b[maxn];
int n,c[maxn],d[maxn];
typedef long long ll;
const ll mod = 1e8 - 3;
ll ans = 0;
void MergeSort(int l,int r) {
if(l >= r)return ;
int mid = l + r >> 1;
MergeSort(l , mid);
MergeSort(mid + 1 , r);
for(int k = l,i = l,j = mid + 1;k <= r;++ k) {
if(j > r||(i <= mid&&d[i] < d[j])) {
c[k] = d[i ++];
}
else c[k] = d[j ++],(ans += mid - i + 1) %= mod;
}
for(int k = l;k <= r;++ k)d[k] = c[k];
return ;
}
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i].x),a[i].id = i;
for(int i = 1;i <= n;++ i)scanf("%d",&b[i].x),b[i].id = i;
sort(a + 1 , a + 1 + n);
sort(b + 1 , b + 1 + n);
for(int i = 1;i <= n;++ i)d[a[i].id] = b[i].id;
MergeSort(1 , n);
printf("%lld",ans);
return 0;
}
完结撒花✿✿ヽ(°▽°)ノ✿