原题
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
有3根木头[232, 124, 456], k=7, 最大长度为114.
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。
解题思路
- 思路：Binary Search
- 问题又可以转化成在1和给的所有原木中最长的长度中间找一个合适的长度，使得把每段原木按此分段后得到的小段木头数目至少为k
- 扩展，除法转化为二分法，求100除以5，相当于在0到100之间找一个数使得x*5小于等于100，(x+1)*5大于100
完整代码
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):
if sum(L) < k:
return 0
start, end = 1, max(L)
while start + 1 < end:
mid = start + (end - start) / 2
pieces = sum([l / mid for l in L])
if pieces >= k:
start = mid
else:
end = mid
if sum([l / end for l in L]) > k:
return end
return start
