183. 木材加工

183. 木材加工

中文English

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。

样例

样例 1

输入:
L = [232, 124, 456]
k = 7
输出: 114
Explanation: 我们可以把它分成114cm的7段，而115cm不可以

样例 2

输入:
L = [1, 2, 3]
k = 7
输出: 0
说明:很显然我们不能按照题目要求完成。

挑战

O(n log Len), Len为 n 段原木中最大的长度

注意事项

木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。

输入测试数据 (每行一个参数)如何理解测试数据？

 二分法

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 not L: return 0
        
        max_num = max(L)
        start, end = 0, max_num
        cut_count = 0  
        
        
        while start + 1 < end:
            cut_count = 0 
            mid = start + (end - start) // 2 
            
            #内嵌循环，取count次数
            for one_l in L:
                cut_count += one_l // mid 
            
            #判断,如果切割的数目小于K的话，说明是mid大了，需要左移
            if (cut_count < k):
                end = mid
            else:
                start = mid 
        
        #最终返回
        return start