首先，明确两个概念：
逆序对：数列a[1],a[2],a[3]…中的任意两个数a[i],a[j] (i<j)，如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对.
逆序数：一个数列中逆序对的总数.
例题一：POJ 1804. 点击打开链接
我这里提供了用Merge_sort的方法求解逆序数，时间复杂度为O(nlogn).
关于归并排序：归并排序是将数列a[l,r]分成两半a[l,mid]和a[mid+1,r]分别进行归并排序，然后再将这两半合并起来。
#include<cstdio>#define N 1000+10int 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:\n%d\n\n",++cas,ans);}return 0;}
例题2：POJ 2299. 点击打开链接
跟上题没有什么区别，但n较大，O（n^2)的算法必然超时，，故必须使用Merge_sort,同时注意要使用 long long 。
#include<cstdio>#define N 500000+10long long 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 n;while(scanf("%d",&n),n){for(int i=0;i<n;i++)scanf("%d",&f[i]);ans=0;Merge_sort(0,n-1);printf("%lld\n",ans);}return 0;}
例题3： hdu 4911. 点击打开链接
这里题目另设条件，只能交换k次，所以，先用Merge_sort求出ans，然后与k进行比较即可（ans<=k ->0 ; ans>k -> ans-k ;）。
#include<cstdio>#define N 500000+10long long 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 n,k;while(scanf("%d%d",&n,&k)==2){for(int i=0;i<n;i++)scanf("%d",&f[i]);ans=0;Merge_sort(0,n-1);if(ans>k) printf("%lld\n",ans-k);else printf("0\n");}return 0;}
每一天都是一个阶梯，是向既定目标迈进的新的一步。
