小树剪发网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)


相关推荐

  • Django Django_django获取post数据

    Django Django_django获取post数据前言我们通常做查询操作的时候,都是通过模型名字.objects的方式进行操作。其实模型名字.objects是一个django.db.models.manager.Manager对象,而Manager

  • hMailServer SSL 配置

    hMailServer SSL 配置

  • oracle 分页查询 优化_oracle分页查询封装

    oracle 分页查询 优化_oracle分页查询封装对于数据库中表的数据的 Web 显示,如果没有展示顺序的需要,而且因为满足条件的记录如 此之多,就不得不对数据进行分页处理。常常用户并不是对所有数据都感兴趣的,或者大部分情 况下,他们只看前几页。 通常有以下两种分页技术可供选择。 1234567Select * from (Select rownumrn,t.* from table t)Where rn>&minnum and rn或者Sel

    2022年10月26日
  • Python贪吃蛇小游戏_Python贪吃蛇代码

    Python贪吃蛇小游戏_Python贪吃蛇代码Python命令行小游戏—贪吃蛇前言一、贪吃蛇游戏初始界面及地图1.游戏初始界面2.游戏地图二、命令符的设置、输出刷新和按键检测1.库支持2.c语言代码3.Python代码(变量初始化及游戏初始化)三、蛇的移动四、蛇的方向控制五、食物的设置六、游戏结束总结前言为了初步学习Python更有兴趣,决定做个学编程大多都会做的小游戏—贪吃蛇,因为是刚刚开始学习,不足之处,希望大家多多指正。一、贪吃蛇游戏初始界面及地图1.游戏初始界面defmune():os.system(“color0a

  • ssm框架过时了吗_Spring Boot

    ssm框架过时了吗_Spring BootSpringSpring是一个开源的免费的框架Spring是一个轻量级的,非入侵式的框架控制反转(IOC),面向切面编程(AOP)支持事务的处理,对框架整合的支持IOC理论UserDaoUserDaoImpUserSeviceUserServiceImp在之前,用户的需求可能会影响原来的代码。使用一个set。public void setUserDao(UserDao userDao){ this.userDao = userDao;}之前是主动创建对象,控制

  • bootstrap 双层模态窗关闭问题[通俗易懂]

    一、页面概况二、问题点点击modal“关闭”按钮后,父modal“关闭”按钮失效点击modal右上角“X”后,父modal会一同关闭三、解决方法重写子modal的hide触发事件hi

发表回复

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

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