3344035_tle.cc

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

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

using namespace std;

int n, len[65];
int used[65], tot;
int can;

bool cmp(int a,int b)
{
	return a > b;
}

void dfs(int pos, int need, int done)
{
	int i;

	if (done==0)
	{
		can = 1;
		return ;
	}
	if (need==tot)
	{
		for (i = 0; i < n; i++)
		{
			if (used[i]==0)
			{
				break;
			}
		}
		if (i==n)
		{
			return ;
		}
		pos = i;
	}
	for (i = pos; !can && i < n; i++)
	{
		if (used[i]||len[i] > need)
		{
			continue;
		}
		if (len[i]==need)
		{
			used[i] = 1;
			dfs(i,tot,done-1);
			used[i] = 0;
			return ;
		}
		else
		{
			used[i] = 1;
			dfs(i+1,need-len[i],done);
			used[i] = 0;
		}
	}
}

int main()
{
	int i, total;

	while (scanf("%d",&n)==1,n)
	{
		total = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d",&len[i]);
			total += len[i];
		}
		memset(used,0,sizeof(used));
		sort(len,len+n,cmp);
		can = false;
		for (i = n; !can&&i > 0; i--)
		{
			if (total % i!=0)
			{
				continue;
			}
			tot = total / i;
			if (len[0] > tot)
			{
				continue;
			}
			dfs(0,tot,i);
		}
		printf("%d\n",tot);
	}
	return 0;
}