直接上题：
Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get?
Example 1:
Input: wood = [5, 9, 7], k = 3
Output: 5
Explanation:
5 -> 5
9 -> 5 + 4
7 -> 5 + 2
Example 2:
Input: wood = [5, 9, 7], k = 4
Output: 4
Explanation:
5 -> 4 + 1
9 -> 4 * 2 + 1
7 -> 4 + 3
binary search ?
/**
* 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. Priorities: 1. Have to get calculatedK >= givenK 2. Meanwhile,
* want to maximize the small piece. One thing not clear: do we have to use
* the given small piece? If we have to, we need to concern about the
* shortest wood piece. See commentted-out part In this problem, however, we
* can abandon the small pieces, as long as the max_small_pieces can allow
* calculatedK >= givenK. Use binary search on the largest item: 1. if
* calculatedK < givenK: end = mid; 2. If calculated >= givenK, move start =
* mid as much as possible, which gives maximized small piece.
start = 0, end = 5, wrong 4
L [5], k = 1
*/
public int woodCut(int[] L, int k) {
int end = 0;
for (int len : L) {
end = Math.max(end, len);
}
if (numWood(end, L) >= k) {
return end;
}
// trying to cut with length 1 - max
int start = 0;
while (start + 1 < end) {
int mid = start + ((end - start) >>> 1);
int numMid = numWood(mid, L);
if (numMid >= k) {
start = mid;
} else {
end = mid;
}
}
return start;
}
private int numWood(int length, int[] L) {
int count = 0;
for (int len : L) {
count += len / length;
}
return count;
}