#include<iostream>
#define N 5000
using namespace std;

int a[N],b[N];

void MergeSort(int left,int right,__int64 &count)
{
	if(left<right)
	{
		int mid=(left+right)/2;
		MergeSort(left,mid,count);
		MergeSort(mid+1,right,count);
		int i=left,j=mid+1,k=left;
		while(i<=mid&&j<=right)
			if(a[i]<a[j]) b[k++]=a[i++];
			else 
			{
				count=count+mid-i+1;
				b[k++]=a[j++];
			}
			while(i<=mid)
				b[k++]=a[i++];
			while(j<=right)
				b[k++]=a[j++];
			for(i=left;i<=right;i++)
				a[i]=b[i];
	}
}

int main()
{
	int i,n;
	__int64 count;
	cin>>n;
	while(n)
	{
		for(i=0;i<n;i++)
			cin>>a[i];
		count=0;
		MergeSort(0,n-1,count);
        printf("%I64d\n",count);
		cin>>n;
	}
	return 0;
}

• n < 500,000 (11) Hacker_QC 2010-03-02 17:16:28
• Re:Runtime Error了好多次，不知道问题出在哪里？ (831) 11072215 2012-08-15 21:04:36