poj2299——Ultra-QuickSort

题意：给定若干数，问需多少次调换，可以变成升序数组。

思路：运用归并排序，计算需调换次数。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
__int64 step,a[500005],tt[500005];
void merge(__int64 a[],int left,int mid,int right)
{
	int i=left,j=mid+1,p=left;
	while(i<=mid&&j<=right)
	{
		if(a[i]<=a[j])
		{
			tt[p++]=a[i++];
		}
		else 
		{
			tt[p++]=a[j++];
			step+=mid-i+1;//左、右半部分已排序好，a[i]往后的数值全都大于a[j]  
		}
	}
	while(i<=mid)
		tt[p++]=a[i++];
	while(j<=right)
		tt[p++]=a[j++];
	for(int k=left;k<=right;k++)
	{
		a[k]=tt[k];
	}
}
void mergesort(__int64 a[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=(p+r)/2;
	mergesort(a,p,q);
	mergesort(a,q+1,r);
	merge(a,p,q,r);
	}
}
void solve()
{
	int i;step=0;
	mergesort(a,0,n-1);
	printf("%I64d\n",step);
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		for(int i=0;i<n;i++)
			scanf("%I64d",&a[i]);
		solve();
	}
	return 0;
}