小木棍
题目:https://ac.nowcoder.com/acm/problem/50243
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。
输入描述:
第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为N个用空格隔开的正整数,表示N根小木棍的长度。
输出描述:
输出仅一行,表示要求的原始木棍的最小可能长度。
样例1
输入
9
5 2 1 5 2 1 5 2 1
输出
6
备注:
1<=N<=60
题解:这是一道搜索题,这道题的思路是在拼接木棍时,如果上一个木棍拼完,那么就从下一根最长的木棍拼起,如果没拼完,就从最大的开始拼,如果最大的接上过长就往小试探,当已经减掉了这根木棍的长度时,就不需要往下继续找了。
#include <bits/stdc++.h> typedef long long ll; using namespace std; int n,tong[105],sum,a[105],MAX,ok=1,len,MIN; int dfs(int cur,int x,int y) { if(cur==0) ok=1; if(ok==1) return 0; if(y==0) { dfs(cur-1,MAX,len); return 0; } int i; for(i=x; i>=MIN&&ok==0; --i) { if(tong[i]!=0&&i<=y) { tong[i]--; dfs(cur,i,y-i); tong[i]++; if(y==len||y-i==0) break;//优化1 } } return 0; } int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j; while(cin>>n&&n!=0) { memset(tong,0,sizeof(tong)); sum=0,MAX=0,MIN=99; for(i=1; i<=n; i++) { cin>>a[i]; if(a[i]>50) continue; sum+=a[i]; tong[a[i]]++; MAX=max(MAX,a[i]); MIN=min(MIN,a[i]); } for(i=MAX; i<=sum/2; i++)//优化2 { if(sum%i!=0) continue; len=i; ok=0; dfs(sum/i,MAX,i); if(ok) { cout<<i<<endl; break; } } if(i>sum/2) cout<<sum<<endl; } return 0; }