2250207_ac_546ms_3656k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
using namespace std;

const int MAX = 500001;
long a[MAX], b[MAX];
__int64 res;

void merge(int begin,int mid,int end)
{
	int i, j, k = 0;
	
	for(i = begin, j = mid+1; i <= mid && j <= end; k++)
	{
		if(a[i] <= a[j])
			b[k] = a[i++];
		else 
		{
			b[k] = a[j++];
			res += mid+1-i;
		}
	}
	for(; i <= mid; i++)
		b[k++] = a[i];
	for(; j <= end; j++)
		b[k++] = a[j];
	for(i = 0; i < k; i++)
		a[begin+i] = b[i];
}

void msort(long s, long t)
{
	if(s < t)
	{
		long m = (s+t)>>1;
		msort(s,m);
		msort(m+1,t);
		merge(s,m,t);
	}
}

int main()
{
	long n, i;
	
	while (scanf("%ld",&n),n)
	{
		res = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%ld",&a[i]);
		}
		msort(0,n-1);
		printf("%I64d\n",res);
	}
	return 1;
}