# Wood Cut

Leave a commentSeptember 29, 2016 by oneOokay

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.

start为1，能切的最小的长度，end为最长的木头长度。判断条件为：当切的长度为mid时

- 如果切出来的块数多余k：说明长度小了，长度可以继续增加，此时把start = mid。
- 如果切出来的块数小于k：说明长度太大了，应该减小长度，此时把end = mid。

如此转换成了一个binary search的问题。

public int woodCut(int[] L, int k) {

int max = Integer.MIN_VALUE; //找到最大值的方法

for (int i = 0; i < L.length; i ++) {

max = Math.max(max, L[i]);

}

int start = 1;

int end = max;

while (start + 1 < end) {

int mid = start + (end – start) / 2;

if (count(L, mid) >= k) { //切多了，于是长度可以变大

start = mid; //把mid赋给start

}else {

end = mid;

}

}

if (count(L, end) >= k) { //从end开始判断起

return end;

}

if (count(L, start) >= k) {

return start;

}

return 0;

}

private int count(int[] L, int length) {

int count = 0;

for (int i = 0; i < L.length; i ++) {

count += L[i] / length;

}

return count;

}