九章算法

描述

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为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), 我们可以使用二分答案来优化枚举木材长度的过程

复杂度分析

public 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;

}

}

更多题解参考：九章算法