2299 Ultra-QuickSort（归并）

合并排序第一次。连环画看着合并看着别人的博客的想法。

http://poj.org/problem?

id=2299

#include <stdio.h>
#include <stdlib.h>

#define MAX 500001

int n,a[MAX], t[MAX];
long long int  sum;

//归并
void Merge(int l, int m, int r)
{
    int p=0;
    int i=l, j=m+1;

    while(i<=m && j<=r)
    {
        if(a[i]>a[j])
        {
            t[p++]=a[j++];
            sum+=m-i+1;
        }
        else
        {
            t[p++]=a[i++];
        }
    }

    while(i<=m) t[p++]=a[i++];
    while(j<=r) t[p++]=a[j++];

    for(i=0; i<p; i++)
    {
        a[l+i]=t[i];
    }
}

//归并排序
void MergeSort(int l, int r)
{
    int m;
    if(l<r)
    {
        m=(l+r)/2;
        MergeSort(l,m);
        MergeSort(m+1,r);
        Merge(l,m,r);
    }
}

int main()
{
    int i;
    while(1)
    {
        scanf("%d",&n);
        if(n == 0)
            break;
        sum=0;
        for(i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        MergeSort(0, n-1);
        printf("%lld\n",sum);
    }
    return 0;
}

代码实现參考：http://www.slyar.com/blog/poj-2299-c.html

解题思路參考：http://blog.****.net/lyy289065406/article/details/6647346

版权声明：本文博主原创文章，博客，未经同意不得转载。