这道题一开始我想的是在排序之后只在头和尾往中间靠近来找木块， 然后就WA， 事实证明这种方法是错误的。
然后参考了别人的博客。发现别人是直接暴搜， 但是加了很多剪枝， 所以不会超时。
我也想过这个做法，但是因为觉得肯定超时所以没有写， 我显然没有想到可以这么剪枝
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 1123;
int a[MAXN], vis[MAXN], sum, n, start;
bool dfs(int cnt, int pos, int sum, int ans)
{
if(cnt == n) return true;
REP(i, pos, n)
{
if(vis[i]) continue;
if(sum + a[i] < ans)
{
vis[i] = 1;
if(dfs(cnt + 1, i + 1, sum + a[i], ans)) return true;
vis[i] = 0;
while(a[i + 1] == a[i] && i + 1 < n) i++;
}
else if(sum + a[i] == ans)
{
vis[i] = 1;
if(dfs(cnt + 1, 0, 0, ans)) return true;
vis[i] = 0;
return false;
}
if(sum == 0) return false;
}
return false;
}
int main()
{
while(~scanf("%d", &n) && n)
{
sum = 0;
REP(i, 0, n)
{
scanf("%d", &a[i]);
sum += a[i];
}
sort(a, a + n, greater<int>());
for(int i = n; i > 0; i--)
if(sum % i == 0 && sum / i >= a[0])
{
memset(vis, 0, sizeof(vis));
if(dfs(0, 0, 0, sum / i))
{
printf("%d\n", sum / i);
break;
}
}
}
return 0;
}