把距离的式子搞一搞：$$\sum_i(a_i-b_i)^2=\sum_i(a_i^2+b_i^2)-2\sum_i a_i\times b_i$$
要让距离最小，就要让$\sum_i a_i\times b_i$最大。由排序不等式可知，两列数字中大小顺序对应的相乘，最后再相加的总和最大。这里是证明
于是我们离散化一下，考虑邻项交换使两个排列相等最少需要多少次。
考虑固定一个排列，操作另一个排列。
为什么可以这样做呢？首先，我们设$a$在①态，$b$在②态。假设我们的最优解是一个操作序列$P$，那么我们把对$a$的操作$S$单独拿出来先完成，使$a$到达了③态。这时候你会发现，其余的对$b$的操作$T$也使$b$到达了③态。那其实我们可以只对$b$操作，就是先$T$再$bar{S}$（反着做$S$），这是可行的。
接下来考虑如何安排这个操作？既然$b$中的每个位置都有了自己的目标位置，那我们当然可以给它们重新赋上目标位置的值，然后跑逆序对了。
这个程序是用归并排序求的逆序对。
程序（100分）：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> #define IL inline #define RG register #define _1 first #define _2 second using namespace std; typedef long long LL; const int N=1e5; const LL mod=1e8-3; int n; struct Node{ int d,x; }p[N+3],q[N+3]; IL bool cmp1(Node a,Node b){return a.d<b.d;} IL bool cmp2(Node a,Node b){return a.x<b.x;} int a[N+3]; IL void init(){ for(int i=1;i<=n;i++) p[i].d=q[i].d=i; sort(p+1,p+n+1,cmp2); sort(q+1,q+n+1,cmp2); for(int i=1;i<=n;i++) q[i].x=p[i].d; sort(q+1,q+n+1,cmp1); for(int i=1;i<=n;i++) a[i]=q[i].x; } int t[N+3]; LL cnt; void msort(int l,int r){ if(l>=r) return ; int mid=(l+r)>>1; msort(l,mid); msort(mid+1,r); for(int i=l,j=mid+1,k=l;k<=r;k++) if(j>r||(i<=mid&&a[i]<a[j])) t[k]=a[i++]; else { t[k]=a[j++]; cnt=(cnt+(LL)(mid-i+1))%mod; } for(int i=l;i<=r;i++) a[i]=t[i]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i].x); for(int i=1;i<=n;i++) scanf("%d",&q[i].x); init(); cnt=0; msort(1,n); printf("%lld",cnt); return 0; }
原文：https://www.cnblogs.com/Hansue/p/12901193.html
