不用考虑输入的数据大于50的情况吧



#include <stdio.h>
#include <stddef.h>


int sticks[64];
int used[64];
int count;
int len;
int flag;
int total;


void sort(int* taget, int sum)
{
	int i, j, temp;
	int flag;
	for (i=sum-1, flag=1; i>0 && flag==1; --i)
	{
		flag = 0;
		for (j=0; j<i; j++)
		{
			if (taget[j] < taget[j+1])
			{
				temp = taget[j];
				taget[j] = taget[j+1];
				taget[j+1] = temp;
				flag = 1;
			}
		}
	}
}


void search(int now, int index, int number)
{
	int i, temp;
	for (i=index+1; i<count; i++)
	{
		if (number > 1 && used[i-1] == 0 && used[i] == used[i-1])
		{
			continue;
		}
		if (used[i] == 0)
		{
			temp = now + sticks[i];
			if (temp > len)
			{
				continue;
			}
			else
			{
				if (temp < len)
				{
					used[i] = 1;
					search(temp, i, number);
					if (flag == 1)
					{
						return;
					}
					else
					{
						used[i] = 0;
					}
				}
				else
				{
					if (number == total)
					{
						flag = 1;
						return;
					}
					else
					{
						used[i] = 1;
						search(0, 0, number+1);
						if (flag == 1)
						{
							return;
						}
						else
						{
							used[i] = 0;
							return;
						}
					}
				}
			}
		}
	}
}

int main()
{
	int max, sum, i;

	while (scanf("%d", &count) && count!= 0)
	{
		max = sum = 0;
		for (i=0; i<count; i++)
		{
			scanf("%d", &sticks[i]);
			sum += sticks[i];
			used[i] = 0;
		}
		sort(sticks, count);
		if (sticks[0] == sticks[count-1])
		{
			printf("%d\n", sticks[0]);
			continue;
		}
		max = sticks[0];
		for (i=max+1; i<sum; i++)
		{
			if (sum % i == 0)
			{
				total = sum / i;
				flag = 0;
				len = i;
				used[0] = 1;
				search(sticks[0], 0, 1);
				if (flag == 1)
				{
					printf("%d\n", len);
					break;
				}
			}
		}
		if (flag == 0)
		{
			printf("%d\n", sum);
		}
	}
	return 0;
}

• Re:为什么是WA？上面的测试数据我都试过啦，没错呀，还有特殊的测试数据吗？ (2194) yueliang 2007-04-08 19:46:13