涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: $ \sum(a_i-b_i)^2$
其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
共三行,第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
输出文件为 match.out。
输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。
输入样例
4
2 3 1 4
3 2 1 4
输出样例
1
数据范围 — 对于 10%的数据, 1 ≤ n ≤ 10;
对于 30%的数据,1 ≤ n ≤ 100;
对于 60%的数据,1 ≤ n ≤ 1,000;
对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤ maxlongint
跟大多数人一样,看到题目就有了思路,只是不会证明… 大概就是将上下两行rank值相同的排到一起。我们只需要对a数组记个rank,对b数组记个pos,再找逆序对就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=99999997;
ll __read(){
ll Value=0,Base=1;char Ch=getchar();
for(;!isdigit(Ch);Ch=getchar())if(Ch=='-')Base=-1;
for(;isdigit(Ch);Ch=getchar())Value=Value*10+(Ch^'0');
return Value*Base;
}
const ll maxn=100010;
struct node{
ll val,index;
bool operator <(const node& rhs)
const{
return val<rhs.val;
}
}a[maxn],b[maxn];
ll num[maxn],p[maxn],q[maxn];
ll tmp[maxn],ans;
void Merge_sort(int l,int r){
if(l==r)return ;
ll mid=(l+r)>>1,i=l,j=mid+1,h=l;
Merge_sort(l,mid),Merge_sort(mid+1,r);
while(i<=mid && j<=r){
if(num[i]<=num[j])tmp[h++]=num[i++];
else tmp[h++]=num[j++],(ans+=mid-i+1)%=mod;
}
while(i<=mid)tmp[h++]=num[i++];
while(j<=r)tmp[h++]=num[j++];
for(int k=l;k<=r;k++)num[k]=tmp[k];
}
int main( ){
ll m,n,j,k,i;
n=__read();
for(i=1;i<=n;i++)
a[i].val=__read(),a[i].index=i;
for(i=1;i<=n;i++)
b[i].val=__read(),b[i].index=i;
sort(a+1,a+n+1);sort(b+1,b+n+1);
for(i=1;i<=n;i++)
p[i]=a[i].index,q[b[i].index]=i;
for(i=1;i<=n;i++)
num[i]=p[q[i]];
Merge_sort(1,n);
printf("%lld\n",ans);
return 0;
}