每日一道算法之--在 D 天内送达包裹的能力

二分法

Word count: 704Reading time: 2 min

 2020/05/09   Share

在 D 天内送达包裹的能力

力扣第1011题 : https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/

传送带上的包裹必须在 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 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

二分法求解

这道题我是完全看题解的,因为我一开始的思路全是往动态规划上想了,在状态转移方程上想了很久,还是没有思路,然后去看了一下题解,恍然大悟.

首先知道最小重量肯定是weights数组元素的最小值,最大重量为weights的总和.
在这个限制里,可以用二分法,利用限制的重量来求出天数,在和给定的D作比较,就可以求出最后的解.

代码如下:

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low = max(weights)
        high = sum(weights)
        # 只有一个元素的时候
        if low == high:
            return low
        while low < high:
            # 二分法假设限制的重量
            mid = low + int((high - low) >> 1)
            days = self.get_days(weights, mid)
            # 如果天数大于目标，说明重量限制偏小，移动左边界
            if days > D:
                low = mid + 1
            # 否则,说明重量限制偏大，移动右边界
            else:
                high = mid
        return low
    
    def get_days(self, weights, limit):
        # 记录每天搬运重量的列表，长度为天数
        record = []
        # 记录在重量限制范围内能运输的重量
        r = 0
        for w in weights:
            if r + w <= limit:
                r += w
            else:
                # 如果r + w超出范围,则将r加入记录列表
                record.append(r)
                r = w
        # 这里需要注意,记录列表还要加入最后一个元素
        record.append(r)
        return len(record)

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/05/09/algorithm-1011/

发表日期：May 9th 2020, 11:00:44 am

更新日期：May 9th 2020, 11:01:48 am

Next Post

每日一道算法之--Pow(x, n)
Previous Post

每日一道算法之--杨辉三角

CATALOG

1. 在 D 天内送达包裹的能力
1. 1.1. 二分法求解

