183 · 木材加工 - LintCode

Difficulty
Hard
Tags
二分查找
URL
https://www.lintcode.com/problem/183/
Star
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。给定L和k，你需要计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。
Example 1
输入:
L = [232, 124, 456]
k = 7
输出: 114
Explanation: 我们可以把它分成114cm的7段，而115cm不可以
Example 2
输入:
L = [1, 2, 3]
k = 7
输出: 0
说明:很显然我们不能按照题目要求完成。

二分法

思路
按照分割的长度进行二分，可以有以下几种初始情况，任选一种
notion imagenotion image
题解
class Solution:
    """
    @param L: Given n pieces of wood with length L[i]
    @param k: An integer
    @return: The maximum length of the small pieces
    """
    def woodCut(self, L, k):
        # write your code here
        if len(L) <= 1:
            return L[0] // k if len(L) == 1 else 0

        left, right = 1, max(L)

        while left <= right:
            # 按照每根木头长度 为mid 分, 可以分出来 pieces 根木头
            mid = left + (right - left) // 2
            pieces = self.cutWood(L, mid)
            
            # 数目少了，应该减少 每根木头长度
            if pieces < k:
                right = mid - 1
            else:
                left = mid + 1

        return right

    def cutWood(self, L, length):
        # 切木头，返回可以按照每根长度为length 切出来的数量
        count = 0
        for wood in L:
            count += wood // length
        return count