题解 P1966 【火柴排队】

这道题折腾了一个晚上，最后终于弄出来了 思路见代码最后的注释段 然后至于逆序对的个数怎么求，模拟一下就好了 代码还是很友好的 注意一个点，就是归并排序的时候统计逆序对的个数不是++，而是+=mid-左指针+1（查了我半个多小时，改了就对了） ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; struct huochai{ int h;//高度 int num;//序号 }a[100001],b[100001]; int n; int read() { char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); int h=0; while(ch<='9'&&ch>='0') { h=h*10+ch-48; ch=getchar(); } return h; } int my(const huochai&a,const huochai&b) { if(a.h<b.h) return 1; else return 0; } int c[100001],r[100001],tot=0; void merge_sort(int left,int right) { if(left==right) return; int mid=(right+left)/2,x=left,y=mid+1,t=left; merge_sort(left,mid); merge_sort(mid+1,right); while(x<=mid&&y<=right) { if(r[x]>r[y]) { tot+=mid-x+1;//重点！！！ tot%=99999997; c[t++]=r[y++]; } else c[t++]=r[x++]; } while(x<=mid) c[t++]=r[x++]; while(y<=right) c[t++]=r[y++]; for(int w=left;w<=right;w++) r[w]=c[w]; } int main() { n=read(); for(int i=1;i<=n;i++) a[i].h=read(); for(int i=1;i<=n;i++) a[i].num=i; for(int i=1;i<=n;i++) b[i].h=read(); for(int i=1;i<=n;i++) b[i].num=i; sort(a+1,a+n+1,my); sort(b+1,b+n+1,my); for(int i=1;i<=n;i++) r[a[i].num]=b[i].num; //归并求逆序对 merge_sort(1,n); cout<<tot; return 0; } //本题思路： //先来证明一个公式：若a1>a2且b1>b2，则有(a1-b1)^2+(a2-b2)^2<(a2-b1)^2+(a1-b2)^2 // 当然这个公式很容易证，拆开就好了 // 然后运用这个公式，发现为保证火柴距离最小，两列火柴对应的两根火柴在各列中高度的排名应该相同 //再来定义一个r数组，使得r[a[i].num]=b[i].num,则可以很惊奇地发现，交换次数即为r数组中逆序对的个数，此题得解 ```