涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：
，其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
intput：
4
2 3 1 4
3 2 1 4
output：
1
思路：
先开一个结构体,然后输入。按照v的大小升序排序。
1 const int maxn=100010; 2 struct cyc 3 { 4 int V,id; 5 }a[maxn],b[maxn];
然后，将a中元素对应b的的位置储存到c。
最后，归并排序即可。
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<iomanip> 8 #include<queue> 9 using namespace std; 10 const int maxn=100010,lln=99999997; 11 struct cyc 12 { 13 int v,id; 14 }a[maxn],b[maxn]; 15 int n; 16 int c[maxn],d[maxn]; 17 int ans=0; 18 bool myc(cyc x,cyc y) 19 { 20 return x.v<y.v; 21 } 22 void work(int l,int r) 23 { 24 int mid,tmp,i,j; 25 if(l+1<r) 26 { 27 mid=(l+r)/2; 28 work(l,mid-1); 29 work(mid,r); 30 tmp=l; 31 for(i=l,j=mid;i<=mid-1&&j<=r;) 32 { 33 if(c[i]>c[j]) 34 { 35 d[tmp++]=c[j++]; 36 ans=1LL*(ans+mid-i)%lln; 37 } 38 else 39 { 40 d[tmp++]=c[i++]; 41 } 42 } 43 if(j<=r) 44 { 45 for(;j<=r;j++) d[tmp++]=c[j]; 46 } 47 else 48 { 49 for(;i<=mid-1;i++) d[tmp++]=c[i]; 50 } 51 for(i=l;i<=r;i++) 52 c[i]=d[i]; 53 } 54 else{ 55 if(l+1==r) 56 { 57 if(c[l]>c[r]) 58 { 59 swap(c[l],c[r]); 60 ans=1LL*(ans+1)%lln; 61 } 62 } 63 } 64 } 65 int main() 66 { 67 /*freopen("2.in","r",stdin); 68 freopen("2.out","w",stdout);*/ 69 //ios::sync_with_stdio(false); 70 cin>>n; 71 for(int i=1;i<=n;i++) 72 { 73 cin>>a[i].v; 74 a[i].id=i; 75 } 76 for(int i=1;i<=n;i++) 77 { 78 cin>>b[i].v; 79 b[i].id=i; 80 } 81 sort(a+1,a+1+n,myc); 82 sort(b+1,b+1+n,myc); 83 for(int i=1;i<=n;i++) 84 c[b[i].id]=a[i].id; 85 work(1,n); 86 cout<<ans<<endl; 87 return 0; 88 }