http://poj.org/problem?id=3063
#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 solutionn" );
else
printf( "%c %.2lfn", c, ans*100 );
}
return 0;
}