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

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

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

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