实话是,首先看到这个题目,我就不会,然后看了结题报告,了解了一个知识就是 逆序数
http://blog.csdn.net/lyy289065406/article/details/6647346
我主要加以说明的是关于逆序次数相加的地方
这归并过程中,请注意,j
前面实际上是没有位置的了,因为一发现满足的就被放到 辅助数组中去了,所以,下一次从j 移动到 i 实际上就是只要移动 min-i+1 个位置就可以啦
#include<stdio.h> __int64 sum; int a[5000005]; int b[5000005]; void merge(int begin,int min,int end) { int i=begin,j=min+1,k=begin; while(i<=min && j<=end) if(a[i]>a[j]) { b[k++]=a[j++]; sum+=(min+1-i);//这里就是逆序次数相加的地方,这里不能用j-i,假设a有n个数,b有m个数, //每次就是将b的第一个比较a中的第i个,如果要移动,就是移动n-i+1个位置,此时 //的n 就是min ..所以就是min-i+1 } else b[k++]=a[i++]; while(i<=min) b[k++]=a[i++]; while(j<=end) b[k++]=a[j++]; for(int q=begin;q<=end;q++) a[q]=b[q]; } void Msort(int begin,int end) { if(begin<end) { int min=(begin+end)/2; Msort(begin,min); Msort(min+1,end); merge(begin,min,end); } } int main() { int N; while(scanf("%d",&N),N) { sum=0; for(int i=0;i<N;i++) scanf("%d",&a[i]); Msort(0,N-1); printf("%I64d\n",sum); } return 0; }