poj 2299 遞歸排序

一個數列，隻能交換相鄰兩個數值來排序，計算需要的交換數目使得序列有序。

在歸并排序的同時計算需要交換的數值。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int a[500005],N,T[500005];
long long count(int x,int y)
{
    if(x<y)
    {
        int m=(x+y)>>1,p=x,q=m+1,s=x;
        long long cnt=count(x,m)+count(m+1,y);
        while(p<=m || q<=y)
        {
            if(q>y ||(p<=m&&a[p]<=a[q]))
            {
                T[s++]=a[p++];
                cnt+=(q-m-1);
            }
            else T[s++]=a[q++];
        }
        for(int i=x;i<=y;i++)a[i]=T[i];
        return cnt;
    }
    return 0;
}
int main()
{
//    freopen("test.txt","r",stdin);
    while(scanf("%d",&N)&&N)
    {
        for(int i=0;i<N;i++)
            scanf("%d",&a[i]);
        printf("%lld\n",count(0,N-1));

    }
    return 0;
}