• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode(9)在D天内送达包裹的问题(中等)

开发技术 开发技术 1周前 (05-04) 4次浏览

问题描述:

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码:

class Solution {
public int shipWithinDays(int[] weights, int D) {
// 确定二分查找左右边界
int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
while (left < right) {
int mid = (left + right) / 2;
// need 为需要运送的天数
// cur 为当前这一天已经运送的包裹重量之和
int need = 1, cur = 0;
for (int weight : weights) {
if (cur + weight > mid) {
++need;
cur = 0;
}
cur += weight;
}
if (need <= D) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/zai-d-tian-nei-song-da-bao-guo-de-neng-l-ntml/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

需要注意的:使用二分法查找最小运载能力 其中左边界为最小值即单个包裹最大总量 右边界为最大值即所有包裹总量总和

接下来用贪心算法求最小运载能力,直到左右边界相等时输出结果。


程序员灯塔
转载请注明原文链接:LeetCode(9)在D天内送达包裹的问题(中等)
喜欢 (0)