描述
涵涵有两盒火柴，每盒装有 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=;
int n,data[],ans,y[];
struct pp{
int data,pos,ca;
};
pp a[],b[];
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)>>;
mergesort(l,mid);
mergesort(mid+,r);
int i=l;
int j=mid+;
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+)%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=;i<=n;i++)
{
scanf("%d",&a[i].data);
a[i].pos=i;
}
for (int i=;i<=n;i++)
{
scanf("%d",&b[i].data);
b[i].pos=i;
}
sort(a+,a++n,comp);
sort(b+,b++n,comp);
for (int i=;i<=n;i++)
a[i].ca=b[i].pos;
sort(a+,a++n,comp2);
for (int i=;i<=n;i++)
data[i]=a[i].ca;
mergesort(,n);
cout<<ans;
return ;
}
啊，对，要注意 ans+=(mid-i+1)%mm 与 ans=(ans+mid-i+1)%mm; 的区别