Wood Cut

Leave a comment

September 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;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: