Wood Cut

    Example

    For L=[232, 124, 456], k=7, return 114.

    Note

    You couldn’t cut wood into float length.

    Challenge

    O(n log Len), where Len is the longest length of the wood.

    理清题意后我们就来想想如何用算法的形式表示出来，显然在计算如2, 1, 4等分片数时我们进行了取整运算，在计算机中则可以使用下式表示：
    \sum _{i = 1} ^{n} \frac {L[i]}{l} \geq k

    其中 l 为单段最大长度，显然有 1 \leq l \leq max(L[i]). 单段长度最小为1，最大不可能超过给定原材料中的最大木材长度。

    P.S. 关于二分搜索总结在 Binary Search 一小节，直接套用『模板二——最优化』即可。

    Python

    Java

    定义私有方法C为切分为 x 长度时能否大于等于 k 段。若满足条件则更新, 由于 lb 和 ub 的初始化技巧使得我们无需单独对最后的 lb 和 ub 单独求和判断。九章算法网站上的方法初始化为1和某最大值，还需要单独判断，虽然不会出bug, 但稍显复杂。这个时候lb, ub初始化为两端不满足条件的值的优雅之处就体现出来了。

    复杂度分析

    遍历求和时间复杂度为 O(n), 二分搜索时间复杂度为 O(\log max(L)). 故总的时间复杂度为 O(n \log max(L)). 空间复杂度 O(1).