小树剪发网1114_aow把抓

小树剪发网1114_aow把抓乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。输入格式输入包含多组数据,每组数据包括两行。第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。第二行是截断以后,所得到的各节木棍的长度。在最后一组数据之后,是一个零。输出格式为每组数据,分别输出原始木棒的可能最小长度

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序,帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式
输入包含多组数据,每组数据包括两行。

第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。

第二行是截断以后,所得到的各节木棍的长度。

在最后一组数据之后,是一个零。

输出格式
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。

数据范围
数据保证每一节木棍的长度均不大于 50。

输入样例:
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例:
6
5

题解
深搜dfs,各种剪枝,减枝不会的看上篇文章。每次决定是否开一个新的木棒,注意,头木棒和尾木棒如果策略不行则直接返回false,因为我们可以总是可以把中间的木棒等价交换到头或者末尾

#include<bits/stdc++.h>
using namespace std;
const int N = 70;
int n,m;
int a[N],w[N];
int sum,len;
int vis[N];
bool cmp(const int &a,const int &b){ 

return a > b;
}
bool dfs(int u,int k,int start){ 

if(u == n)return true;
if(k == len)return dfs(u,0,0);
for(int i = start;i < n;i ++){ 

if(!vis[i] && k + a[i] <= len){ 

vis[i] = true;
bool f = dfs(u + 1,k + a[i],start + 1);
vis[i] = false;
if(f)return true;
if(k + a[i] == len)return false;
if(k == 0)return false;
i ++;
while(i < n && a[i] == a[i - 1])i ++;
i --;
}
}
return false;
}
int main(){ 

while(cin>>n,n != 0){ 

sum = 0;
memset(vis,0,sizeof vis);
for(int i = 0;i < n;i ++)cin>>a[i],sum += a[i];
sort(a,a + n,cmp);
for(int i = n;i >= 1;i --){ 

if(sum % i == 0 ){ 

len = sum / i;
if(len >= a[0] && dfs(0,0,0)){ 

cout<<len <<endl;
break;
}
}
}
}
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168663.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Qualcomm QXDM工具简介和log抓取[通俗易懂]

    Qualcomm QXDM工具简介和log抓取[通俗易懂]高通工具简介QXDM简介QXDM安装QXDM激活QXDM使用AT打开Diagnostic口QXDM配置1MessageViewConfigurationMessagePacketsLogPacketsLogPacketsOTAEventReportsStrings2…

  • uni-app打包成安卓app步骤详解[通俗易懂]

    前置:开发环境AndroidStudio下载地址:AndroidStudio官网ORAndroidStudio中文社区HBuilderXApp离线SDK下载:最新android平台SDK下载3.1.10版本起需要申请Appkey,具体请点击链接正文:通过uni-app实现一套代码在微信小程序和安卓端app同时适配1.创建文件创建Demo文件,采用uni-app模板2.创建应用在https://dev.dcloud.net.cn/app页面创建相同名称的应用,并且获取

  • eclipse配置SVN_eclipse导入svn项目

    eclipse配置SVN_eclipse导入svn项目当我们使用EclipseSVN插件进行团队合作开发时,有些时候我们可能想要将某个文件的本地版本与服务器上的最新版本(或历史版本)进行对比,以便于查找出改动的不同之处。1、与SVN服务器上的最新版本进行对比。右键单击指定的项目,在弹出的关联菜单中点击【Team】->【SynchronizewithRepository】,此时Eclipse将进入同步视图。在团队同步视图中,点击左侧任意文件,

    2022年10月14日
  • idea2021.7.15版激活码【中文破解版】[通俗易懂]

    (idea2021.7.15版激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlMLZPB5EL5Q-eyJsaWNlbnNlSW…

  • 【逆向】QQkey盗号木马原理分析

    【逆向】QQkey盗号木马原理分析一、简介QQkey是一段字符串,通过这段字符串在没有QQ登录密码的前提下你依然能够在浏览器中对别人QQ空间、邮箱等应用进行随意访问和操作。现在市面上已经有很多使用易语言编写的盗号木马,专门盗取别人的

  • J2EE架构师手册

    J2EE架构师手册 

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号