题目描述

现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？

输入

输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000），表示序列的长度，当n=0时，输入结束。
接下来的n行，每行一个整数a[i]（0<=a[i]<=999999999），表示序列中第i个元素。

输出

对于每组输入，输出使得所给序列升序的最少交换次数。

样例输入

5
9
1
0
5
4
3
1
2
3
0

样例输出

6
0

代码

#include <cstdio>
const int maxn=500010;
int a[maxn],b[maxn];
long long num;
void Merge(int a[],int start,int mid,int end)
{
    int i=start,j=mid+1,k=start;
    while(i<=mid&&j<=end)
    {
        if(a[i]<=a[j])
        {
            b[k++]=a[i++];
        }
        else
        {
            num+=j-k;
            b[k++]=a[j++];
        }
    }
    while(i<=mid)
    {
        b[k++]=a[i++];
    }
    while(j<=end)
    {
        b[k++]=a[j++];
    }
    for(int i=start;i<=end;i++)
    {
        a[i]=b[i];
    }
}
void MergeSort(int a[],int start,int end)
{
    if(start<end)
    {
        int mid=(start+end)/2;
        MergeSort(a,start,mid);
        MergeSort(a,mid+1,end);
        Merge(a,start,mid,end);
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        num=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        MergeSort(a,0,n-1);
        printf("%lld\n",num);
    }
    return 0;
}