首页 > 小木棍
开通博客写题解
头像 秃头大太阳
发表于 2020-06-08 10:11:01
题目描述 乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。 输入描述: 第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二 展开全文
去ta的博客 赞 (9) 回复(4) 收起
头像 zjnu_tjq
发表于 2020-06-28 08:30:24
链接：https://ac.nowcoder.com/acm/problem/50243 题目描述： 乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CAICAIIs
发表于 2019-08-31 13:49:06
题目描述乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。 输入描述:第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-06-09 22:54:39
题目意思 乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。 解题思路 参考秃头大太阳题解深度优先搜索加减枝。首先我们从第一根 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 瑜画
发表于 2020-06-06 14:06:22
思路：枚举可能的答案，由于题目要求的是求最小，从小到大开始枚举，最小可能是数组里最大的数，最大可能是数组里面所有数的总和。拼接木棍的过程使用dfs，每次拼接一定找未使用过的最大的木棍进行拼接 做到以上，即可保证答案正确，但是速度还不够，需要进行剪枝。 剪枝1：如果当前小木棍是拼接的整个木棍中的第一个 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-30 15:41:54
采用DFS，每一层递归都是去选择某个木棍去组成一个长木棍。如果能够将小木棍全部用完而且长木棍也正好拼凑成整数的话就可以。这时候可以从小到大进行验证如果某个长木棍的长度可以满足条件那么就是答案。但是直接进行DFS会超时需要进行剪枝。 先将木棍从大到小排序，让每一个长木棍里面的小木棍都从大到小排序 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 阿哲不是吧
发表于 2020-10-06 16:27:58
牛客网poj 1011 题目： George took sticks of the same length and cut them randomly until allparts became at most 50 units long. Now he wants to return stic 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 nanfengjiuchui
发表于 2023-07-29 11:47:53
思路： 要求最短的原长，直接从最长的小木棍枚举到全部小木棍和sum，然后用dfs去看每个枚举的长度是否可行即可，但此处还需要去剪枝： 1、枚举的长度要满足可以被总长sum整除； 2、当一个小木棍放在第一个位置的时候不能满足条件，那么这个时候的枚举长度是不可取的，因为第一个位置是最宽松的，此时不行那么 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Z_L_G
发表于 2025-04-09 14:35:26
题意 给定n根短棍，将其拼成若干等长的长棍，求能拼成的长棍的最短长度是多少 思路 枚举长棍的长度，深搜判断能否拼成（将每一个棍尝试摆上去，如果摆上去不大于枚举长度就深搜下一层，超过的就跳过，最终判断所有棍用完的时候，最后一根长棍是否刚好拼完） 优化一：对于枚举，枚举区间为最长的棍的长度到所有棍 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 默默然诶
发表于 2022-07-28 12:45:29
#include<bits/stdc++.h> using namespace std; int a[70], v[70]; int sum,n; bool cmp(int a, int b) { return a > b; } int dfs(int num, in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”