感谢_Darwin
首先，明确两个概念：
逆序对：数列a[1],a[2],a[3]…中的任意两个数a[i],a[j] (i<j)，如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对.
逆序数：一个数列中逆序对的总数.
传送门POJ1804
题目简述：为一组数排序，只允许交换相邻两数，求排好序要交换的次数
解题思路：每次交换只能减少一个逆序，而且必定能减少一个逆序，从而问题就转换为求逆序个数了。这题数据规模很小，暴力可过。
我这里提供了用Merge_sort的方法求解逆序数，时间复杂度为O(nlogn).
关于归并排序：归并排序是将数列a[l,r]分成两半a[l,mid]和a[mid+1,r]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设l<=i<=mid，mid+1<=j<=r），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数。
#include<cstdio> #define N 1000+10 int ans=0; int f[N],t[N]; void Merge(int l,int m,int r) //左右两个表合并成一个表 { int i=l,j=m+1,cnt=0; while(i<=m && j<=r) { if(f[i]<=f[j]) t[cnt++]=f[i++]; else { ans+=m-i+1; t[cnt++]=f[j++]; //核心代码，求解逆序数个数。 } } while(i<=m) //若左表不空 t[cnt++]=f[i++]; while(j<=r) //若右表不空 t[cnt++]=f[j++]; for(int k=0;k<cnt;) //修改原数组 f[l++]=t[k++]; } void Merge_sort(int l,int r) //归并排序 { if(l==r) return ; else { int m=(l+r)>>1; Merge_sort(l,m); Merge_sort(m+1,r); Merge(l,m,r); } } int main() { int T,cas=0; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&f[i]); ans=0; Merge_sort(0,n-1); printf("Scenario #%d: %d ",++cas,ans); } return 0; }
例题2：POJ 2299. 点击打开链接
跟上题没有什么区别，但n较大，O（n^2)的算法必然超时，故必须使用Merge_sort,同时注意要使用 long long
例题3：例题3： hdu 4911. 点击打开链接
题意：
inversion,求倒序数变形
规定最多交换k次，求交换后序列的逆序数 LL
#include "cstdio" #define N 500010 #define LL long long LL ans=0; LL f[N],t[N]; void Merge(int l,int m,int r) { int i=l,j=m+1,cnt=0; while(i<=m&&j<=r) { if(f[i]<=f[j]) { t[cnt++]=f[i++]; } else { ans+=m-i+1; t[cnt++]=f[j++]; } } while(i<=m)t[cnt++]=f[i++]; while(j<=r)t[cnt++]=f[j++]; for(int k=0;k<cnt;k++) f[l++]=t[k]; } void Merge_sort(int l,int r) { if(l==r) return ; int m=(l+r)/2; Merge_sort(l,m); Merge_sort(m+1,r); Merge(l,m,r); } int main() { int t,n,k; while(~scanf("%d%d",&n,&k)&&n) { for(int i=0;i<n;i++) scanf("%lld",&f[i]); ans=0; Merge_sort(0,n-1); if(ans<=k) ans=0; else ans-=k; printf("%lld ",ans); } }