posts - 100,  comments - 15,  trackbacks - 0
#include<iostream>
using namespace std;
#define MAXN 500000
int x[MAXN+1];
int z[MAXN+1];
__int64 reverse;

void merge(int low,int mid,int high)
{
    
int i=low,j=mid+1,q=0;
    
while (i<=mid && j<=high)
    
{
          
if (x[i]<=x[j])
                z[q
++]=x[i++];
          
else {
                z[q
++]=x[j++];
                reverse
+=mid-i+1;
          }

    }

    
while (i<=mid)
          z[q
++]=x[i++];
    
while (j<=high)
          z[q
++]=x[j++];
    
for(i=0;i<q;i++)
          x[low
+i]=z[i];
}


void mergesort(int low,int high)
{
    
int mid;
    
if ( low< high)
    
{
          mid
=(low+high)/2;
          mergesort(low,mid);
          mergesort(mid
+1,high);
          merge(low,mid,high);
    }

}



int main()
{
    
int n,i;
    
while(scanf("%d",&n)==1 && n!=0)
    
{
        
for(i=0;i<n;i++)
            scanf(
"%d",&x[i]);
        reverse
=0;
        mergesort(
0,n-1);
        printf(
"%I64d\n",reverse);


    }

    
return 0;
}
posted on 2009-07-12 14:59 wyiu 阅读(93) 评论(0)  编辑 收藏 引用 所属分类: POJ

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