LeetCode 1011. 在 D 天内送达包裹的能力

◎

本节目标

固定船的容量后按原顺序贪心装载，用所需天数判断容量是否可行。

这道题是二分答案解题框架的第二道母题。它展示了常见组合：外层二分最小容量，内层用贪心扫描判断这个容量需要多少天。

查看原题

题意与约束

传送带上的包裹必须按数组 weights 的原顺序装船。每天可以连续装若干个包裹，但总重量不能超过船的运载能力。求在 days 天内送完全部包裹所需的最小运载能力。

不能调整包裹顺序，也不能拆分一个包裹。一个候选容量是否足够，取决于按原顺序装载时最少需要多少天。

朴素思路与瓶颈

可以从最重包裹 M 起逐个尝试容量直到总重量 S，但每个容量都要扫描全部包裹，最坏需要 O(n(S - M + 1))。容量越大，可运输所需天数不会增加，因此应二分第一个可行容量。

固定容量后如何判断

给定容量 capacity，从第一件包裹开始扫描：

1. 当前包裹还能装进当天，就加入当天载荷；
2. 加入后会超载，就从当前包裹开始新的一天；
3. 若所需天数超过 days，立即判定容量不可行。

这种“能装就继续装”的策略会让每天承载尽可能长的连续前缀。

为什么贪心天数最少

考虑任意一天。按顺序装载的前提下，贪心方案已经装入该容量允许的最长前缀。任何其他合法方案都不可能在这一天多装下一件，否则贪心也能装入它；如果更早停下，只会把更多包裹留给后面的天数。

因此，逐日使用最长可装前缀不会比任何其他方案使用更多天。扫描得到的 requiredDays(capacity) 就是该容量下的最少天数，可以作为可靠的可行性判断。

为什么具有单调性

容量增加后，每天原本能装下的包裹仍然能装下，还可能多装一些，所以最少所需天数不会增加：

小容量：不可行，不可行，……
边界：第一个可行容量
大容量：可行，可行，……

若某个容量能在 days 天内完成，所有更大的容量也能完成。题目因此转化为寻找第一个使 requiredDays(capacity) <= days 成立的容量。

答案上下界

• 下界是最重包裹：容量小于它时，这件包裹永远无法装船。
• 上界是所有包裹重量之和：一次装完，必然能在一天内完成。

两端都来自必要或充分条件，因此真实答案一定在：

[max(weights), sum(weights)]

中。C++ 用 long long 保存总和、中点和当天载荷，避免累计重量溢出。

循环不变量与正确性

循环维护最小可行容量始终位于闭区间 [left, right]：

• mid 可行时，它可能是第一个可行容量，所以令 right = mid；
• mid 不可行时，更小容量也不可能可行，所以令 left = mid + 1。

区间最终收缩到唯一值。它既没有被不可行区间排除，又是所有保留可行值中最小的，因此就是答案。

代码实现

C++ 的 canShip(weights, days, capacity) 显式接收包裹数组、天数和候选容量；Python 的 can_ship(capacity) 通过闭包捕获 weights 和 days，只显式接收候选容量。两者都不读取输入流，也不修改输入；每天载荷即将超限时先增加天数，再把当前包裹放到新的一天。

C++

C++17

#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        long long left = *max_element(weights.begin(), weights.end());
        long long right = accumulate(weights.begin(), weights.end(), 0LL);

        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return static_cast<int>(left);
    }

private:
    bool canShip(const vector<int>& weights, int days, long long capacity) {
        int requiredDays = 1;
        long long load = 0;

        for (int weight : weights) {
            if (load + weight > capacity) {
                requiredDays++;
                load = 0;
            }
            load += weight;
            if (requiredDays > days) {
                return false;
            }
        }
        return true;
    }
};

Python

Python 3

class Solution:
    def shipWithinDays(self, weights, days):
        def can_ship(capacity):
            required_days = 1
            load = 0
            for weight in weights:
                if load + weight > capacity:
                    required_days += 1
                    load = 0
                load += weight
                if required_days > days:
                    return False
            return True

        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if can_ship(mid):
                right = mid
            else:
                left = mid + 1
        return left

复杂度分析

设包裹数为 n，所有包裹总重量为 S，最重包裹为 M。

• 时间复杂度：O(n log(S - M + 1))。每轮可行性判断线性扫描，二分范围为 [M, S]。
• 额外空间：O(1)。只维护二分边界、天数和当天载荷。

边界与易错点

• days = 1 时必须一次装完，答案是所有重量之和。
• days = n 时每件都可单独运输，答案是最大单件重量。
• 包裹必须保持原顺序，不能先排序再分组。
• 新开一天后，当前包裹必须计入新一天，不能在边界处遗漏。
• 下界不能从 0 开始，否则可行性函数还需处理单件包裹无法装入的额外情况。
• 总重量可能超过窄整数的安全范围，累计量和中点应使用足够宽的类型。

迁移方向

这套“固定上限，再贪心计算最少分组数”的结构可迁移到连续数组分段：例如限制每段和不超过某个候选值，判断能否在指定段数内完成。只要更大的上限不会让最少分组数增加，就能继续二分第一个可行上限。