http://algorithm.yuanbin.me/zh-cn/binary_search/wood_cut.html
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.
public int woodCut(int[] L, int k) {
if (L == null || L.length == 0 || k <= 0) {
return 0;
}
int lo = 1;
int hi = 0;
for (int i = 0; i < L.length; i++) {
hi = Math.max(hi, L[i]);
}
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
int pieces = getPieces(mid, L);
if (pieces < k) {
hi = mid - 1;
} else {
lo = mid;
}
}
if (getPieces(lo, L) >= k) {
return lo;
} else {
return 0;
}
}
private int getPieces(int len, int[] L) {
int ans = 0;
for (int l : L) {
ans += l / len;
}
return ans;
}
首先来分析下题意，题目意思是说给出 n 段木材L[i], 将这 n 段木材切分为至少 k 段，这 k 段等长，求能从 n 段原材料中获得的最长单段木材长度。以 k=7 为例，要将 L 中的原材料分为7段，能得到的最大单段长度为114, 232/114 = 2, 124/114 = 1, 456/114 = 4, 2 + 1 + 4 = 7.
理清题意后我们就来想想如何用算法的形式表示出来，显然在计算如
2, 1, 4等分片数时我们进行了取整运算，在计算机中则可以使用下式表示：
其中 为单段最大长度，显然有 . 单段长度最小为1，最大不可能超过给定原材料中的最大木材长度。
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;
}
定义私有方法
C为切分为 x 长度时能否大于等于 k 段。若满足条件则更新lb, 由于 lb 和 ub 的初始化技巧使得我们无需单独对最后的 lb 和 ub 单独求和判断。九章算法网站上的方法初始化为1和某最大值，还需要单独判断，虽然不会出bug, 但稍显复杂。这个时候lb, ub初始化为两端不满足条件的值的优雅之处就体现出来了。
遍历求和时间复杂度为 , 二分搜索时间复杂度为 . 故总的时间复杂度为 . 空间复杂度 .
public int woodCut(int[] L, int k) { int max = 0; for (int i = 0; i < L.length; i++) { max = Math.max(max, L[i]); } // find the largest length that can cut more than k pieces of wood. int start = 1, end = max; while (start + 1 < end) { int mid = start + (end - start) / 2; if (count(L, mid) >= k) { start = mid; } else { end = mid; } } if (count(L, end) >= k) { return end; } if (count(L, start) >= k) { return start; } return 0; } private int count(int[] L, int length) { int sum = 0; for (int i = 0; i < L.length; i++) { sum += L[i] / length; } return sum; }
