归并排序求逆序数.doc

《归并排序求逆序数.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Poj2299归并排序求逆序数//归并排序中交换的次数就是逆序数的个数，也可以用树状数组解决#include#include#includelonglongans;inta[];intc[];voidMergeSort(intl,intr){intmid;inti,j;inttmp;if(r>l){mid=(l+r)/2;MergeSort(l,mid);MergeSort(mid+1,r);tmp=l;for(i=l,j=mid+1;i<=mid&&j<=r;){if(a[i]>a[j]){//tmp++;c[

2、tmp++]=a[j++];ans+=mid-i+1;//过程中求逆序数}elsec[tmp++]=a[i++];}if(i<=mid)for(;i<=mid;)c[tmp++]=a[i++];if(j<=r)for(;j<=r;)c[tmp++]=a[j++];for(i=l;i<=r;i++)a[i]=c[i];}}intmain(){inti,j;intn;while(scanf("%d",&n)!=EOF){if(n==0)break;for(i=1;i<=n;i++)scanf("%d",&a[i]);ans=0;MergeSort(1,n);//for(i=

3、1;i<=n;i++)//printf("%d",a[i]);//printf("");printf("%lld",ans);}system("pause");}