Loading...
墨滴

SuperMP

2021/04/26  阅读:86  主题:默认主题

Leetcode刷题 | 第118题:在D天内送达包裹的能力

荷尔蒙决定一见钟情,多巴胺决定天长地久。

1011. 在 D 天内送达包裹的能力[1]

题目:传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天都会按给出重量的顺序往传送带上装载包裹,装载的重量不会超过船的最大运载重量(每一天船来时都是空载状态)。返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1:
输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5, 输出:15
解释:船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
第 1 天:1, 2, 3, 4, 5
第 2 天:6, 7
第 3 天:8
第 4 天:9
第 5 天:10
请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

示例 2:
输入:weights = [3,2,2,4,1,4], D = 3, 输出:6
解释:船舶最低载重 6 就能够在 3 天内送达所有包裹,如下所示:
第 1 天:3, 2
第 2 天:2, 4
第 3 天:1, 4

示例 3:
输入:weights = [1,2,3,1,1], D = 4
输出:3

提示:
1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

分析[2]:因为每天都要装货,所以船的下限载重不会低于最重的那个包裹,且船的上限没必要高于所有包裹的重量和。题目要求在规定时间内,求船的下限载重,这就要求满足两点:一是,时间不能超;二是,下限载重。

因为时间是规定好的,所以可以假设一个下限载重,看需要的时间是否是满足给定的时间。又因为下限载重到上限载重之间的数据可以看作一个升序数组,而在有序数组搜索一个满足条件的数,可以使用二分查找,而没必要依次增加(减少)下限载重进行查找。

Java代码:

class Solution {
    public int shipWithinDays(int[] weights, int d) {
        int left = Arrays.stream(weights).max().getAsInt(); // 船载重下限
        int right = Arrays.stream(weights).sum(); // 船载重上限
        while (left < right) { // 可尝试的搜索区间
            int mid = left + (right - left) / 2// 本次二分搜索的下限载重值
            int needDays = 1, curW = 0;
            for (int w : weights) {
                if (curW + w <= mid) { // 该包裹可以在今天装下
                    curW += w;
                } else { // 该包裹不可以在今天装下
                    ++needDays;
                    curW = w;
                }
                if (needDays > d) break// 及时终止
            }
            if (needDays <= d) { // 是可行解, 但不能确定是否是下限值, 压缩搜索空间
                right = mid;
            } else { // 非可行解, 下限值在本次搜索的最低载重值的基础上 + 1
                left = mid + 1;
            }
        }
        return left;
    }
}
  • 时间复杂度为 ,空间复杂度为

参考资料

[1]

1011. 在 D 天内送达包裹的能力: https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/

[2]

分析: 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/

SuperMP

2021/04/26  阅读:86  主题:默认主题

作者介绍

SuperMP