简要题意

木材店老板给出一个整数 \(m\) 和 \(m\) 个木板的长度。老板给出的木板可以随意无损耗切割。

约翰给出一个整数 \(n\) 和所需要的 \(n\) 个木板的长度。

求约翰能得到最多木板的个数。

(相关资料图)

分析

二分答案的题基本不会是单纯的二分，一般会带上一些优化、DP、搜索等……

这道题主要是运用搜索和剪枝，而且剪枝不止一个。

正常搜索肯定都会写，不过优化比较多。

优化一：贪心

既然木材店的木板都可以任意分割，那么将给出的 m 个木板排序，优先使用长木板。

而对于需要的木板来说，优先使用短木板才能使木板数量最大。

优化二：前缀和

用前缀和维护所需木板长度，记录给出木板总长度。

二分前判断所需木板总长度是否已经大于给出木板总长度，超过就向回退，直到木板足够。

优化三：剪枝一

记录浪费的木材数量。一块长木板被切割后，不使用的那段就可能被浪费。

搜索过程中，如果浪费掉的木材长度与所需木材的长度超过了给出木材总长度，则不继续向下搜索。

优化四：剪枝二

如果需要的两块相邻木板长度相等，我们就可以从上一次放的那一块枚举，可以节省大量计算。

总结

总的来说，这道题是以搜索为辅的二分答案，重点是优化很多。

经过一段时间思考想出了前两个优化，优化三四没想出来。

这道题提供了一种新的类型的节省计算的方法，还是很有价值的。