3105005_ac_46ms_232k.cc

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

#include <stdio.h>
#include <math.h>
#include <string.h>
#define inf 2100000000.0

int c, s, cnt[6];
int mass[11], pos[11], ans[11];
double tot, min, num[6];

void calc()
{
	int i;
	double sum = 0;

	for(i = 1; i <= c; i++)
	{
		num[i] = 0;
	}
	for(i = 1; i <= s; i++)
	{
		num[pos[i]] += mass[i];
	}
	for(i = 1; i <= c; i++)
	{
		sum += fabs(num[i]-tot);
	}
	if(sum < min)
	{
		min = sum;
		memcpy(ans,pos,sizeof(pos));
	}
}

void dfs(int n)
{
	int i;

	if(n==s+1)
	{
		calc();
		return ;
	}
	for(i = 1; i <= c; i++)
	{
		pos[n] = i;
		if(cnt[i]==2)
		{
			continue;
		}
		cnt[i]++;
		dfs(n+1);
		cnt[i]--;
	}
}

int main()
{
	int i, j, cas = 1;

	while(scanf("%d%d",&c,&s)==2)
	{
		printf("Set #%d\n",cas++);
		tot = 0;
		min = inf;
		for(i = 1; i <= s; i++)
		{
			scanf("%d",&mass[i]);
			tot += mass[i];
		}
		tot /= 1.0*c;
		for(i = 1; i <= c; i++)
		{
			cnt[i] = 0;
		}
		dfs(1);
		for(i = 1; i <= c; i++)
		{
			printf(" %d:",i-1);
			for(j = 1; j <= s; j++)
			{
				if(ans[j]==i)
				{
					printf(" %d",mass[j]);
				}
			}
			printf("\n");
		}
		printf("IMBALANCE %.5lf\n\n",min);
	}
	return 0;
}