描述
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少k段的,则返回0即可。
在线评测地址
LintCode 领扣
样例1
输入: L = [232, 124, 456] k = 7 输出: 114 Explanation: 我们可以把它分成114cm的7段，而115cm不可以
样例2
输入: L = [1, 2, 3] k = 7 输出: 0 说明:很显然我们不能按照题目要求完成。
算法：二分
题目意思是说给出n段木材L[i], 将这n段木材切分为至少k段，这k段等长，
若直接枚举每段木材的长度则时间复杂度高达 O(n*maxL), 我们可以使用二分答案来优化枚举木材长度的过程
设left=0,即木材长度最小为0，设right=max_L即所有木材中最长的长度，因为结果是不可能大于这个长度的，mid = left + right 若长度为mid时不能完成，说明太长了，那么我们往区间[left,mid]搜， 若可以完成，说明也许可以更长，那么我们往[mid,right]搜, 在check函数中，我们判断用所有木头除当前mid的值的和是否大于等于k，若小于则说明该mid不可行, 若大于等于则说明mid可行 由于判断条件是left + 1 < right,最后结果就是left的值复杂度分析
时间复杂度O(nlog（n）) 二分查找的复杂度 空间复杂度O(size(L)) 只有数组Lpublic class Solution {
public int woodCut(int[] L, int k) {
int len_L = L.length;
if (len_L == 0) {
return 0;
}
int max_L = 0;
for (int i = 0;i < len_L;i++) {
max_L = Math.max(max_L,L[i]);
}
long left = 0,right = max_L;
int mid;
while (left + 1 < right) {
mid = (int)(left + (right - left) / 2);
if (check(L, k, len_L, mid)) {
left = mid;
}
else {
right = mid;
}
}
if(check(L,k,len_L,(int)right)) return (int)right;
return (int)left;
}
private boolean check(int [] L,int k,int len_L,int mid){
int count = 0;
for (int i = 0;i < len_L;i++) {
count += L[i] / mid;
}
if (count >= k) {
return true;
}
return false;
}
}
更多题解参考：九章算法
