2846856_ac_15ms_204k.cpp

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

#include <stdio.h>
//#include <time.h>
#include <algorithm>

using namespace std;

struct node
{
	int w, b;
}a[10001];
int n;
int mark[10001];
int c, d;

int min(int s,int t)
{
	return s<t?s:t;
}

int main()
{
	int i, t, inf, tot, num;
	int ta, sumw, sumb;
	int tmpb, tmpw;
	char ch;


//	srand((unsigned)time(NULL) );
	while(scanf("%d",&n)==1)
	{
		scanf("%d",&tot);
		sumb = sumw = 0;
		tot = n*tot/2;
		for(i = 1; i <= n; i++)
		{
			scanf("%d%d",&a[i].w,&a[i].b);
			sumw += a[i].w;
		}
		sumb = tot*2 - sumw;
		t = 100;
		inf = -1;
		while(t--)
		{	
			memset(mark,0,sizeof(mark));
			num = tmpb = tmpw = 0;
			while(num<n/2)
			{
				ta = (rand()%n+n)%n+1;
				if(mark[ta]==0)
				{
					num++;
					mark[ta] = 1;
					tmpb += a[ta].b;
					tmpw += a[ta].w;
				}
			}
			if(tmpb*2>tot&&(sumb-tmpb)*2>tot)
			{
				if(min(tmpb,(sumb-tmpb))>inf)
				{
					inf = min(tmpb,(sumb-tmpb));
					ch = 'B';
				}
				continue;
			}
			if(tmpw*2>tot&&(sumw-tmpw)*2>tot)
			{
				if(min(tmpw,(sumw-tmpw))>inf)
				{
					inf = min(tmpw,(sumw-tmpw));
					ch = 'W';
				}
			}
		}
		if(inf==-1)
			puts("No solution");
		else
			printf("%c %.2lf\n",ch,inf*100.0/tot);
	}
	return 0;
}