当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2721小木棍
1016+

题目大意:有n段小木棍,由m根等长木棍砍出来,请问m最大是多少?m最大时原来木棍的长度是多少?

题目描述

原题来自:CERC 1995

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过 50 。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

输入

第一行为一个单独的整数 N 表示砍过以后的小木棍的总数。 第二行为 N 个用空格隔开的正整数,表示 N 根小木棍的长度。

输出

输出仅一行,表示要求的原始木棍的最小可能长度。

提示

样例输入

9
5 2 1 5 2 1 5 2 1

样例输出

6

1N60

解题思路

不难想到枚举原来木根长度,最小是最大那一段,最长是所有木棍总长度。接着就是判断是否可行。这里的顺序查找,不能改成二分,因为长度m不行,比m小的可能可以,比m大的也可能可以。

暴力验证1:枚举长度x,共需要y根木棍,暴力枚举每段木棍属于哪一根,排序后剪枝,比较难拿满分。

暴力验证2:逐根木棍验证,先把第一根木棍确定,再枚举下一根,只要有一根不满足,后面不需要再搜索。

1、首先是每一段木棍从大到小排序,可以尽量把木棍填满;

2、其次是规定,每根木棍的每一小段,都是从大到小的,这样可以避免组合的重复;

3、代码19行:如果木棍段i刚好填满第k跟木棍,那么不需要再搜了,要么找到答案,要么下次找的还是同一根(如果找的是更小的两根,后面也只会更难找到答案);同样的,如果这段是该木根最大的一段,如果找不到答案也没必要再搜,因为这段最大的木棍总需要放在某一根的最底部。

4、代码20行,如果下一根跟当前这一根相同长度,也没必要再搜一遍,该搜的刚才搜过了。

程序实现

SSOJ2721小木棍:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!