2299.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 45 行

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[500000], temp[500000], n;
__int64 ans;
void merge( int l, int r )
{
	int i, j, k, c = (l+r)/2;
	if( l+1 >= r ) return ;
	merge( l, c );
	merge( c, r );
	for( i=l, j=c, k=0; i < c || j < r ;   )
	{
		if( i < c && ( j == r || a[i] < a[j] ) )
		{
			temp[k++] = a[i++];
		}
		else
		{
			temp[k++] = a[j++];
			ans += c-i;
		}
	}
	std::copy( temp, temp+k, a+l );
}
int main()
{
	int i;
	while(1)
	{
		scanf( "%d", &n );
		if( n == 0 ) break;
		for( i = 0; i < n; i++ )
			scanf( "%d", &a[i] );
		ans = 0;
		merge( 0, n );

		printf( "%I64d\n", ans );
	}
	return 0;
}