第一题 permutation
是一道爱斯基摩人的逆序对题（形容它不裸的程度）
如果从上往下看，会发现横线的作用是交换当前它左右两侧的数。因此这道题的第一部分可以直接从上往下暴力swap。
对于第二部分，把这样一张图倒过来看，可以发现倒过来的图也就是把一个排列经过m次交换恢复顺序。
而最少的横线数，也就是最少的交换次数，就是逆序对数。
第一部分模拟交换+第二部分归并排序统计逆序对数 100分
#include<cstdio> using namespace std; const int N=1000007; int n,m,hx[N],a[N],c[N],cnt; void sort(int l,int r) { if(l==r) return; int mid=l+r>>1;int t=l,q=mid+1,p=l-1; sort(l,mid);sort(mid+1,r); while(q<=r&&t<=mid) { if(a[t]>a[q]) { cnt+=mid-t+1; c[++p]=a[q];q++; } else c[++p]=a[t++]; } while(q<=r) c[++p]=a[q++]; while(t<=mid)c[++p]=a[t++]; for(int i=l;i<=r;i++) a[i]=c[i]; } void swap(int &x,int &y) { int temp=x;x=y;y=temp; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&hx[i]); for(int i=1;i<=n;i++) a[i]=i; for(int i=1;i<=m;i++) swap(a[hx[i]],a[hx[i]+1]); for(int i=1;i<=n;i++) printf("%d ",a[i]); sort(1,n); //- for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n%d",cnt); }
考试的时候以为是道图论题，在那方面想了半天没想出来就放弃了。还是太年轻。
原文：https://www.cnblogs.com/IvyLH03/p/11517409.html