归并排序时，对于相临两归并段A[l~m],B[m+1~r]，归并为C[l~r]，若B[i]在C中为C[j]，则它在AB组成的序列中逆序数为i+m+1-l，且由于A、B是分别排好序的，因此i+m+1-l>=0，同时，A中元素不产生逆序数。由此，我们可以简单的在归并排序的算法中加入nReverse+= i+m+1-l;
以POJ2299(http://acm.pku.edu.cn/JudgeOnline/problem?id=2299)为例，代码如下：
#include <iostream>
using namespace std;
int a[1000002],b[1000002];
__int64 num;
void merge(int *a,int p,int q,int r){
int i, j= p;
int startA=p,endA=q-1,startB=q,endB=r;
while( startA<=endA && startB<=endB ){
if(a[startA]<=a[startB]){b[j]=a[startA];j++;startA++;}
else{
b[j++]= a[startB++];
num+= q-startA;//逆序数
}
}
while(startA<=endA){b[j]=a[startA];startA++;j++;}
while(startB<=endB){b[j]=a[startB];startB++;j++;}
for(i=p;i<=r;i++) a[i]=b[i];
}
void msort(int *a,int n){
int n0, seg, lastseg, s0, i, j, m;
n0=n; seg=1; lastseg=1;
num=0;
while( n0>=2 ){
m= n0;//两段合为1段 m段合为n0=m/2段
n0/= 2;
s0= seg*2;
if( (m&1)==0 ){ //有 n0 seg 每seg 长s0
for( i=1,j=0; i<=n0; i++,j+=s0 ){
if(i<n0)merge(a,j,j+seg,j+s0-1);
else merge(a,j,j+seg,n-1);
}
lastseg= seg+lastseg;
seg=s0;
}
else{
for( i=1,j=0; i<=n0; i++,j+=s0 )
merge(a,j,j+seg,j+s0-1);
j= n-lastseg-s0;
merge(a,j,n-lastseg,n-1);
seg= s0; lastseg+= s0;
}
}
}
int main(){
int n, i;
while( scanf("%d",&n) && n ){
num= 0;
for( i= 0; i< n; i++ )
scanf("%ld",&a[i]);
msort(a, n);
printf("%lld\n",num);
}
return 0;
}
此外，1007：DNA Sorting也可以用这样的方法解决
posted on 2009-03-13 14:16
古月残辉 阅读(889)
评论(0) 编辑 收藏 引用 所属分类:
POJ