POJ2299-Ultra-QuickSort

2019/7/24 8:34:19 人评论 次浏览 分类:学习教程

原文链接:http://www.cnblogs.com/YogurtShen/archive/2012/10/18/2729457.html

http://poj.org/problem?id=2299

#include<stdio.h>
int a[500002],left[250001],right[250001];
__int64 count;
void merge(int a[],int l,int m,int r)
{
    int i,j,k,n1,n2;
    n1=m-l+1;
    n2=r-m;
    for(i=0;i<n1;i++)
       left[i]=a[l+i];
    for(i=0;i<n2;i++)
       right[i]=a[m+1+i];
    left[n1]=right[n2]=0x7fffffff;
    i=j=0;
    for(k=l;k<=r;k++)
    {
        if(left[i]<=right[j])
           a[k]=left[i++];
        else
        {
            a[k]=right[j++];
            count+=n1-i;
        }
    }
}
void mergesort(int a[],int l,int r)
{
    if(l<r)
    {
        int m=l+r>>1;
        mergesort(a,l,m);
        mergesort(a,m+1,r);
        merge(a,l,m,r);
    }
}
int main(void)
{
    int n,i;
    while(scanf("%d",&n),n)
    {
        count=0;
        for(i=0;i<n;i++)
           scanf("%d",&a[i]);
        mergesort(a,0,n-1);
        printf("%I64d\n",count);
    }
    return 0;
}

转载于:https://www.cnblogs.com/YogurtShen/archive/2012/10/18/2729457.html

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->