import java.util.Arrays;
public class Algorithm {
public static void main(String[] args) {
int[] weights = {1,2,3,4,5,6,7,8,9,10};
System.out.println(new Solution().shipWithinDays(weights, 5));
}
}
class Solution {
public int shipWithinDays(int[] weights, int days) {
/**
* 最小运输量为所有货物中最重的那个,否则大于它的货物永远不能运载
*/
int minLoad = Arrays.stream(weights).max().getAsInt();
int maxLoad = Arrays.stream(weights).sum();
while (minLoad < maxLoad) {
int load = minLoad + (maxLoad- minLoad) / 2;
if (time(weights, load) > days) {
minLoad = load + 1;
}
else {
maxLoad = load;
}
}
return minLoad;
}
public int time(int[] weights, int load){
int res = 0;
/**
* 初始船数量最少为1
*/
int n = 1;
int i = 0;
while (i < weights.length) {
/**
* 如果货物累计重量小于等于运载量,就累计,再计算下一个货物
*/
if (res + weights[i] <= load) {
res += weights[i];
i++;
}
/**
* 否则当前货物不动,清空累计,再加一艘船来计算
*/
else {
n++;
res = 0;
}
}
return n;
}
}
https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/