首页 > 代码库 > 小木棍 ［数据加强版］
小木棍 ［数据加强版］
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式：
输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1：
95 2 1 5 2 1 5 2 1
输出样例#1：
6
思路：dfs+剪枝
代码实现：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int n,ans; 6 int s[80]; 7 int a[80],b,c; 8 inline int max_(int x,int y){return x>y?x:y;} 9 inline bool cmp(int a,int b){return a>b;}10 bool dfs(int k){11 memset(a,0,sizeof(a));12 for(int i=1;i<=n;i++){13 b=0;14 while(a[b]+s[i]>k) b++;15 a[b]+=s[i];16 }17 for(int i=0;a[i];i++)18 if(a[i]<k) return 0;19 return 1;20 }21 int main(){22 scanf("%d",&n);23 for(int i=1;i<=n;i++){24 scanf("%d",&s[i]);25 if(s[i]>50) i--,n--;26 else ans=max_(ans,s[i]);27 }28 sort(s+1,s+n+1,cmp);29 while(!dfs(++ans));30 printf("%d",ans);31 return 0;32 }
小木棍 ［数据加强版］
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。