Description
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.
中文描述：有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
Example
For L=[232, 124, 456], k=7, return 114.
解题思路：
这道题根据题意， 发现是在一个范围里面求取最大值， 也就是一段木头的最大长度。 那么可以考虑用二分法来解决问题。 那么二分法 左边边界考虑为1。 因为分木头最短的长度（整数）就是1。 最大值应该是数组里的最大值。 既然有了两个边界那么就可以套用二分法的模板了：
int start 1 , end = max; // 1. 找到可行解范围
while(start + 1 < end)
{
int mid = start + (end - start) / 2; // 2. 猜答案
if(check(mid)){ // 3. 检验答案
start = mid; // 4. 调整搜索范围
}else
{
end = mid; // 4. 调整搜索范围
}
}
具体代码如下：
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) {
// write your code here
int start = 1;
int end = 0;
for(Integer item : L)
{
end = Math.max(end, item);
}
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;
}
public int count(int[] L, int len)
{
int sum = 0;
for(int item : L)
{
sum += item / len;
}
return sum;
}
}
count 函数是用来判断所猜的答案是否正确的 因为要分木头 k是份数 长度是mid。 如果可以分 那么返回的sum应该要大于或者等于k， 这样说明长度小了 移到start。 如果小于k， 说明长度分大了， 那么移动end。 最后加两个判断 判断到底是该返回start还是该返回end。
