随笔-20  评论-16  文章-36  trackbacks-0

    归并排序时,对于相临两归并段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 古月残辉 阅读(915) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理