2188.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
int ans,temp[1000], n;
int a[1001],b[1001],id[1001];

void merge( int l, int r )
{
	int c = (l+r)/2, i, j, k;
	if( r-l <= 1 )return;

	merge( l, c );
	merge( c, r );

	for(i = l,j = c,k = l ; i < c || j < r ; )
	{
		if( i < c && ( j >=r || a[i] < a[j] ) )
		temp[k++] = a[i++], ans += j - c;
		else temp[k++] = a[j++];
	}

	for( i=l; i<r; i++ )
	a[i] = temp[i];
}


int main()
{
	int i, y, x;

	scanf( "%d", &n );
	for( i=0; i<n; i++ )
	{
		scanf( "%d %d", &a[i], &b[i] );
	}

	for( i=0; i<n; i++ )
	id[ b[i] ] = i;

	for( i=0; i<n; i++ )
	a[i] = id[ a[i] ];

	ans = 0;

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