Wood Cut

http://www.lintcode.com/en/problem/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.

Notice

You couldn't cut wood into float length.

If you couldn't get >= k pieces, return 0.

Have you met this question in a real interview? Yes

Example

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

Thoughts

数组元素代表长度，找出能切出K或大于K份等长分块的最长的长度。给定背包数K，找能把所有背包撑满的最大容量。二分范围，让end为范围的upper_bound, 对mid统计能切出的份数，当大于等于K时让start = mid + 1。最后start停在解的upper_bound上，因此再减一。

Code

class Solution {
public:
    int woodCut(vector<int> &L, int k) {
        long start = 1, end = 0;
        for (int l : L) {
            end = max(end, (long)l);
        }
        ++end;
        const auto count = [&](int x) {
            int res = 0;
            for (const auto l : L) {
                res += l / x;
            }
            return res;
        };
        while (start < end) {
            long mid = start + (end - start) / 2;
            if (count(mid) >= k) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start - 1;
    }
};

Analysis

时间复杂度O(lg()