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.

分析：

这是二分法第三重境界的典型，思维方式就是我这个长度肯定是从0到max(L[i])之间波动的，注意不是min(L[i])而是0。然后，用这个作为上下界，进行二分法，可以满足log(n)的复杂度。

解法：

class Solution {
public:
    bool isValidCut(vector<int> L, int k, int n) {
        int sum = 0;
        for (int i = 0; i < L.size(); i++) {
            sum += (L[i] / n);
        }
        return (sum >= k);
    }

    int woodCut(vector<int> L, int k) {
        // write your code here
        if (L.size() == 0) {
            return 0;
        }

        int start = 0;
        int end = INT_MIN;
        for (int i = 0; i < L.size(); i++) {
            end = max(end, L[i]);
        }

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isValidCut(L, k, mid) ) {
                start = mid;
            } else {
                end = mid;
            }
        } 

        if (isValidCut(L, k, end) ) {
            return end;
        } else {
            return start;
        } 
    }
};