题目：https://www.luogu.com.cn/problem/P1966
首先分析题目定义的距离式子：
∑ i = 1 n ( a i ? b i ) 2 \sum_{i = 1}^{n}(a_i-b_i)^2 i=1∑n?(ai??bi?)2
是不是没有头绪？
再化简一下：
∑ i = 1 n a i 2 ? 2 a b + b i 2 \sum_{i = 1}^{n}{a_i}^2-2ab+{b_i}^2 i=1∑n?ai?2?2ab+bi?2
= ∑ i = 1 n a i 2 + b i 2 ? ∑ i = 1 n 2 a b =\sum_{i = 1}^{n}{a_i}^2+{b_i}^2 - \sum_{i = 1}^n2ab =i=1∑n?ai?2+bi?2?i=1∑n?2ab
很显然 ∑ i = 1 n a i 2 + b i 2 \sum_{i = 1}^{n}{a_i}^2+{b_i}^2 ∑i=1n?ai?2+bi?2 是不会变的，于是要使 ∑ i = 1 n ( a i ? b i ) 2 \sum_{i = 1}^{n}(a_i-b_i)^2 ∑i=1n?(ai??bi?)2 最小，让 ∑ i = 1 n 2 a b \sum_{i = 1}^n2ab ∑i=1n?2ab 最大即可。
易证很容易猜到当两个序列按升序或降序排列后，可以使 ∑ i = 1 n 2 a b \sum_{i = 1}^n2ab ∑i=1n?2ab 取最小值，这种想法是正确的（我太菜，不会严格证明）。
所以这道题就转换成：给定两个数列，要使两个数列中大小排名相等的元素一一对应（数列 a a a 第一大的数对应数列 b b b 第一大的数，数列 a a a 第二大的数对应数列 b b b 第二大的数，以此类推），求最小的交换次数。
首先定义一个结构体， n u m num num 表示数组元素的值， i d id id 表示数组元素在原来序列中的位置。读入的时候记录一下 i d id id，再将 a a a b b b 两数组升序排序。
那么该怎么求最小交换次数呢？
先来把玩一下样例二：
| ? 原数组 ? | ? 排序后? | |
|---|---|---|
| ? a n u m a_{num} anum?? | ? 1 3 4 2? | ? 1 2 3 4 ? |
| ? a i d a_{id} aid? ? | ? 1 2 3 4 ? | ? 1 4 2 3? |
| ? b n u m b_{num} bnum?? | ? 1 7 4 2? | ? 1 2 4 7? |
| ? b i d b_{id} bid? ? | ? 1 2 3 4 ? | ? 1 4 3 2 ? |
定义一个数组 c c c，有 c [ a [ i ] . i d ] = b [ i ] . i d c[a[i]_ {.id}]=b[i]_ {.id} c[a[i].id?]=b[i].id?
由上表可知：
c [ a [ 1 ] . i d ] = b [ 1 ] . i d , c [ 1 ] = 1 c[a[1]_ {.id}]=b[1]_ {.id} , c[1]=1 c[a[1].id?]=b[1].id?,c[1]=1
c [ a [ 2 ] . i d ] = b [ 2 ] . i d , c [ 4 ] = 4 c[a[2]_ {.id}]=b[2]_ {.id} , c[4]=4 c[a[2].id?]=b[2].id?,c[4]=4
c [ a [ 3 ] . i d ] = b [ 3 ] . i d , c [ 2 ] = 3 c[a[3]_ {.id}]=b[3]_ {.id} , c[2]=3 c[a[3].id?]=b[3].id?,c[2]=3
c [ a [ 4 ] . i d ] = b [ 4 ] . i d , c [ 3 ] = 2 c[a[4]_ {.id}]=b[4]_ {.id} , c[3]=2 c[a[4].id?]=b[4].id?,c[3]=2
所以 c c c 数组就是 [ 1 , 3 , 2 , 4 ] [1,3,2,4] [1,3,2,4]（其实就是个双关键字排序）。
我们知道当 a [ i ] . i d = b [ i ] . i d a[i]_ {.id}=b[i]_ {.id} a[i].id?=b[i].id? 时， c i = i c_i=i ci?=i。
所以 ? i , c i = i ?i,c_i=i ?i,ci?=i 时， a a a、 b b b 数组排序前的值的排名一一对应。
于是原问题就进一步转换成了：给定序列 c c c，每次可翻转其中两个数，求最小的翻转次数，使得序列 c c c 升序排序。
这不就是求逆序对吗？
用归并排序就能轻松解决。
AC code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
template<class T>inline void read(T &s){
int f=1; s=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();s*=f;
}
const int MAXN=1e5+10;
const int md=1e8-3;
ll c[MAXN],q[MAXN],ans;
int n;
struct node{
int num,id;inline void rd(int i){
read(num),id=i;};
}a[MAXN],b[MAXN];
void merge_sort(int l,int r){
if(l==r) return;int mid=(l+r)>>1;merge_sort(l,mid),merge_sort(mid+1,r);int head1=l,head2=mid+1;for(int i=l;i<=r;i++){
if(head2<=r&&(head1>=mid+1||c[head1]>c[head2]))q[i]=c[head2++];else q[i]=c[head1++],ans+=(head2-mid-1)%md; } for(int i=l;i<=r;i++) c[i]=q[i];
}
inline bool cmp(const node&x,const node&y){
return x.num<y.num;
}
signed main(){
ios::sync_with_stdio(false);read(n);for(int i=1;i<=n;i++) a[i].rd(i);for(int i=1;i<=n;i++) b[i].rd(i);sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp);for(int i=1;i<=n;i++)c[a[i].id]=b[i].id;merge_sort(1,n);cout<<ans%md;return 0;
}
完结撒花~