题目描述

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

输入

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

输出

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

代码

#include<bits/stdc++.h>
using namespace std;
long long x[500005],y[500005];
int ans=0;
void msort(int l,int r)
{
	if(l==r)
		return ;
	int mid=(l+r)/2;
	msort(l,mid);
	msort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid && j<=r)
	{
		if(x[i]<=x[j])
		{
			y[k] = x[i];
			i++;
			k++;
		}
		else
		{
			y[k] = x[j];
			j++;
			k++;
			ans += mid-i+1;
		}
	}
	while(i<=mid)
	{
		y[k] = x[i];
		i++;
		k++;
	}
	while(j<=r)
	{
		y[k] = x[j];
		j++;
		k++;
	}
	for(int z=l;z<=r;z++)
		x[z] = y[z];
	return ;
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0)
			break;
		for(int i=1;i<=n;i++)
			cin>>x[i];
		msort(1,n);
		printf("%d\n",ans);
		ans = 0;
	}
	
	return 0;
}

五十分