题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式：
输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1：
9
5 2 1 5 2 1 5 2 1
输出样例#1：
6 思路：
大搜索；
（思路来源：http://blog.csdn.net/chai_jing/article/details/52450419） 来，上代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n,len[],cnt,maxlen,ans,Len,tot; bool if_[],if_re; bool dfs(int now,int le,int num)
{
if(num==tot+) return false;
if(le==)
{
if(num==tot) return true;
return dfs(,Len,num+);
}
for(int i=now+;i<=n;i++)
{
if(le-len[i]>=)
{
if(!if_[i])
{
if_[i]=true;
if(dfs(i,le-len[i],num)) return true;
if_[i]=false;
if(len[i]==le) break;
if(le==Len) break;
while(len[i+]==len[i]) i++;
}
}
}
return false;
} bool check(int lenth)
{
Len=lenth;
tot=cnt/lenth;
for(int i=;i<=n;i++) if_[i]=false;
return dfs(,Len-len[],);
} bool cmp(int a,int b)
{
return a>b;
} int main()
{
int n_,pos;
scanf("%d",&n_);
for(int i=;i<=n_;i++)
{
scanf("%d",&pos);
if(pos<=)
{
maxlen=max(pos,maxlen);
len[++n]=pos,cnt+=pos;
}
}
sort(len+,len+n+,cmp);
for(int i=maxlen;i<=cnt;i++)
{
if(cnt%i==&&check(i))
{
ans=i;
break;
}
}
cout<<ans;
return ;
}