Thinking process
Find the largest number that satisfy cutwood(num) >= k
O (n log max)
Mistakes
where to start? where to end?
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 || k == 0) return 0;
int start = 1;
int end = 1;
for (int i = 0; i < L.length; ++i) {
end = Math.max(L[i], end);
}
while (start + 1 < end) {
int mid = (end - start) / 2 + start;
if (cutWood(mid, L) == k) {
start = mid;
} else if (cutWood(mid, L) < k) {
end = mid;
} else {
start = mid;
}
}
if (cutWood(end, L) >= k) return end;
if (cutWood(start, L) >= k) return start;
return 0;
}
private int cutWood(int length, int[] L){
int result = 0;
for (int i = 0; i < L.length; ++i) {
result += L[i] / length;
}
return result;
}
}