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.

http://www.lintcode.com/en/problem/wood-cut/

Discussion

最大长度是所有L[i]里面最大的，记为right，最小left=0； 然后二分查找即可。左右移动的标准是按当前长度（mid）得到的piece count是大于k还是小于k

Solution

class Solution {
public:
    /** 
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    int woodCut(vector<int> L, int k) {
        // write your code here
        if(L.size() == 0 | k <= 0) {
        return 0;
        }
        int peak = INT_MIN;
        for(int i=0; i<L.size(); i++) {
            //totalLen += L[i] / k;
            peak = max(peak, L[i]);
        }
        int left = 0;
        int right = peak;
        int pieceNum = 0;
        while(left + 1 < right ) {
            int mid = left + (right - left) / 2;
            pieceNum = 0;
            for(int i=0; i<L.size(); i++) {
                pieceNum += L[i] / mid;
            }
            if(pieceNum < k) {
                right = mid;
            } else {//大于等于k的时候都要右移，因为要找最大的长度
                left = mid;
            }
        }
        int maxlen = right;
        pieceNum = 0;
        for(int i=0; i<L.size(); i++) {
            pieceNum += L[i] / maxlen;
        }
        if(pieceNum >=k ) {
            return right;
        }
        return left;
    }
};