Wood Cut

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

Example

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

Solution

给定了L是一个木板数组，给定了需要切成的块数，求解能切最大长度的最少的等长木板数。

（1）最后取的能切的最大长度，所以不可能超过木板中的最长的那根，

所以start = 1 最小长度，end = 最大长度，（二分法问题，索引，具体的数值 都可以作为求解的依据。）

（2） 这里的mid , 可以间接的求出可以切出多少块木板，这样就可以得出，如果当前的mid 宽度可以切出的木板数量，如果大于了给定的K块，则说明需要切出更少的块数，则需要增加长度，这样，start ＝ mid 注解：12月26日，二分法不一定用数组索引同时也可以用尺寸单位，二分法的基本就是排除法，考虑这道题是否可以使用DP来实现。

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):
        # very important here, we are supposed the min = 1 not 0.1 or deciaml value
        if sum(L) < k:
            return 0
        start, end = 1, max(L)
        while start + 1 < end:
            mid = ( start + end ) / 2
            pieces = sum( l / mid for l in L )
            if pieces >= k :
                start = mid
            else:
                end = mid
        # why is greater and equal k instead of == k, because it may cannot cut right into k piece
        if sum(l / end for l in L) >= k:
            return end
        return start