SSOJ2721小木棍
1537+
作者：crxis 发布：2020-12-31 分类：深度优先搜索
题目大意：有n段小木棍，由m根等长木棍砍出来，请问m最大是多少？m最大时原来木棍的长度是多少？
题目描述
原题来自：CERC 1995
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50 。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入
第一行为一个单独的整数 N 表示砍过以后的小木棍的总数。 第二行为 N 个用空格隔开的正整数，表示 N 根小木棍的长度。
输出
输出仅一行，表示要求的原始木棍的最小可能长度。
提示
样例输入
9
5 2 1 5 2 1 5 2 1样例输出
61≤N≤60
解题思路
不难想到枚举原来木根长度，最小是最大那一段，最长是所有木棍总长度。接着就是判断是否可行。这里的顺序查找，不能改成二分，因为长度m不行，比m小的可能可以，比m大的也可能可以。
暴力验证1：枚举长度x，共需要y根木棍，暴力枚举每段木棍属于哪一根，排序后剪枝，比较难拿满分。
暴力验证2：逐根木棍验证，先把第一根木棍确定，再枚举下一根，只要有一根不满足，后面不需要再搜索。
1、首先是每一段木棍从大到小排序，可以尽量把木棍填满；
2、其次是规定，每根木棍的每一小段，都是从大到小的，这样可以避免组合的重复；
3、代码19行：如果木棍段i刚好填满第k跟木棍，那么不需要再搜了，要么找到答案，要么下次找的还是同一根（如果找的是更小的两根，后面也只会更难找到答案）；同样的，如果这段是该木根最大的一段，如果找不到答案也没必要再搜，因为这段最大的木棍总需要放在某一根的最底部。
4、代码20行，如果下一根跟当前这一根相同长度，也没必要再搜一遍，该搜的刚才搜过了。
程序实现
