> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/er-fen-range/wood-cut.md).

# 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

```cpp
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()