3063.txt

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

Source

Problem Id:3063  User Id:fzk 
Memory:52K  Time:218MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <stdlib.h>

int m, n;
int s0[5000], s1[5000];
int mem[2][10000], *a = mem[0], *b = mem[1];
int w0, w1, b0, b1, sum;

#define mine( a, b ) ((a)<(b)?(a):(b))

void fill( ) {
	int i;
	int m0 = 0, m1 = 0;
	w0 = w1 = b0 = b1 = 0;
	for( i=0; i<n; i++ ) {
		if( m1 == n/2 ) {
			w0 += a[i];
			s0[m0++] = i;
		}
		else if( m0 == n/2 ) {
			w1 += a[i], b1 += b[i];
			s1[m1++] = i;
		}
		else if( a[i] > b[i] ) {
			if( w0-b0<w1-b1 ) {
				w0 += a[i], b0 += b[i];
				s0[m0++] = i;
			}
			else {
				w1 += a[i], b1 += b[i];
				s1[m1++] = i;
			}
		}
		else {
			if( w0-b0>w1-b1 ) {
				w0 += a[i], b0 += b[i];
				s0[m0++] = i;
			}
			else {
				w1 += a[i], b1 += b[i];
				s1[m1++] = i;
			}
		}
	}
	sum = n/2*m;
	return;
}


double random( int count ) {
	int i, j, k;
	int nw0, nw1;
	double r, t;
	r = mine( 1.0*w0/sum, 1.0*w1/sum );
	while( count-- ) {
		i = rand()%(n/2);
		j = rand()%(n/2);
		nw0 = w0-a[s0[i]]+a[s1[j]];
		nw1 = w1-a[s1[j]]+a[s0[i]];
		
		t = mine( 1.0*nw0/sum, 1.0*nw1/sum );

		if( t > r ) {
			k = s0[i]; s0[i] = s1[j]; s1[j] = k;
			w0 = nw0, w1 = nw1;
			r = t;
		}
	}
	return r;
}


int main( ) {
	int i, *temp;
	double ans, t;
	char c;

	while( scanf( "%d", &n ) == 1 ) {

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

		ans = random( n*1000 );
		c = 'W';

		temp = a; a = b; b = temp;

		fill( );
		t = random( n*1000 );
		if( t > ans )
			ans = t, c = 'B';

		if( ans <= 0.5 )
			printf( "No solution\n" );
		else
			printf( "%c %.2lf\n", c, ans*100 );
	}
	return 0;
}