# Wood Cut

## Question

### Problem Statement

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.

#### Note

You couldn't cut wood into float length.

#### Challenge

O(n log Len), where Len is the longest length of the wood.

## 题解 - 二分搜索

Warning 注意求和与取整的顺序，是先求 L[i]/l的单个值，而不是先对L[i]求和。

P.S. 关于二分搜索总结在 Binary Search 一小节，直接套用『模板二——最优化』即可。

### Python

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):
if sum(L) < k:
return 0

start, end = 1, max(L)
while start + 1 < end:
mid = (start + end) / 2
pieces_sum = sum(len_i / mid for len_i in L)
if pieces_sum < k:
end = mid
else:
start = mid

if sum(len_i / end for len_i in L) >= k:
return end
return start


### C++

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) {
int lb = 0, ub = 0;
for (auto l : L) if (l + 1 > ub) ub = l + 1;

while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (C(L, k, mid)) lb = mid;
else ub = mid;
}
return lb;
}

int C(vector<int> L, int k, int mid) {
int sum = 0;
for (auto l : L) {
sum += l / mid;
}
return sum >= k;
}
};


### Java

public 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.
*/
public int woodCut(int[] L, int k) {
if (L == null || L.length == 0) return 0;

int lb = 0, ub = Integer.MIN_VALUE;
// get the upper bound of L
for (int l : L) if (l > ub) ub = l + 1;

while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (C(L, k, mid)) {
lb = mid;
} else {
ub = mid;
}
}

return lb;
}

// whether it cut with length x and get more than k pieces
private boolean C(int[] L, int k, int x) {
int sum = 0;
for (int l : L) {
sum += l / x;
}
return sum >= k;
}
}