描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑i=1n(ai−bi)2∑i=1n(ai−bi)2，其中 aiai 表示第一列火柴中第 i 个火柴的高度，bibi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
格式
输入格式
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出格式
输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。
样例2
样例输入2[复制]
4
1 3 4 2
1 7 2 4
样例输出2[复制]
2
解题报告
刚拿到这道题的时候有一点懵，好吧可能自己现在能力不够。
这道题先快排得到两个对应序列是距离最小的（这点是想到了的），记录第二组的位置排序，然后将第一组序列按原位置排列同时将对应的那一组序列排好序，以这组的位置序列为归并序列求逆序对。（好像有点乱，下面来讲解）
a.data:1 3 4 2 a.pos:1 2 3 4
b.data:1 7 2 4 b.pos:1 2 3 4
排序(a,b,data)后
a.data:1 2 3 4 a.pos:1 4 2 3
b.data:1 2 4 7 b.pos:1 3 4 2
记录对应a.ca: 1 3 4 2
排序(a,pos)后
data=a.ca:1 4 2 3
然后归并 求逆序对
代码附下
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int mm=99999997; int n,data[100005],ans,y[100005]; struct pp{ int data,pos,ca; }; pp a[100005],b[100005]; int comp(const pp&a,const pp&b) { return a.data<=b.data; } int comp2(const pp&a,const pp&b) { return a.pos<=b.pos; } void mergesort(int l,int r) { if (l==r) return ; int mid=(l+r)>>1; mergesort(l,mid); mergesort(mid+1,r); int i=l; int j=mid+1; int o=l; while (i<=mid||j<=r) { if (j>r||i<=mid&&data[i]<=data[j]) y[o++]=data[i++]; else { y[o++]=data[j++]; ans=(ans+mid-i+1)%mm;//WA ans+=(mid-i+1)%mm } } while(i<=mid) y[o++]=data[i++]; while (j<=r) y[o++]=data[j++]; for (int i=l;i<=r;i++) data[i]=y[i]; } int main() { freopen("match.in","r",stdin); freopen("match.out","w",stdout); cin>>n; for (int i=1;i<=n;i++) { scanf("%d",&a[i].data); a[i].pos=i; } for (int i=1;i<=n;i++) { scanf("%d",&b[i].data); b[i].pos=i; } sort(a+1,a+1+n,comp); sort(b+1,b+1+n,comp); for (int i=1;i<=n;i++) a[i].ca=b[i].pos; sort(a+1,a+1+n,comp2); for (int i=1;i<=n;i++) data[i]=a[i].ca; mergesort(1,n); cout<<ans; return 0; }
前者要错最后两组数据 后者不会
多复习复习归并排序
好像还可以用树状数组，还有冒泡排序；
如果有时间再写。