运送包裹为什么能二分船容量？如何写可行性检查？

简化版

运送包裹二分的是船的容量 capacity。容量越大，需要的天数越少；如果某个容量能在 D 天内运完，那么更大的容量也一定能运完，所以可行性单调。下界是最大单个包裹重量，上界是所有包裹总重量。对容量二分，用贪心模拟每天尽量装，计算所需天数，找最小可行容量。

详细版

这题的 can(cap) 很关键：按原顺序遍历包裹，当前天能装就继续装，装不下就开新的一天。因为包裹顺序不能变，所以不能排序，也不能随意组合。若所需天数 days <= D，说明容量 cap 可行。

int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) {
        lo = Math.max(lo, w);
        hi += w;
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

boolean canShip(int[] weights, int days, int cap) {
    int need = 1, cur = 0;
    for (int w : weights) {
        if (cur + w > cap) {
            need++;
            cur = 0;
        }
        cur += w;
    }
    return need <= days;
}

复杂度是 O(n log S)，S 是容量搜索范围。面试要强调下界不能取 1，因为容量小于最大包裹时那个包裹永远装不上。

完整版教学

一、题目的约束决定了不能排序

运送包裹看起来像装箱问题，但题目要求包裹必须按给定顺序装船。这一点非常重要：你不能把重包裹和轻包裹重新排列，也不能为了凑容量打乱顺序。因此可行性检查不是任意组合，而是从左到右顺序扫描。

例如 weights=[3,2,2,4,1,4]，容量为 6 时，顺序装载可能是 [3,2]、[2,4]、[1,4]，需要 3 天。若打乱顺序，也许能凑出别的组合，但那不是题目允许的方案。面试中先说清这个前提，后面的贪心模拟才站得住。

约束	影响
包裹顺序不能变	只能从左到右扫描
每天容量固定	超过容量就开新一天
要最小容量	在答案空间找左边界

二、容量为什么具有单调可行性

容量越大，每天能装的包裹只会更多，不会更少，所以需要的天数单调不增。若容量 15 能在 D 天内完成，容量 16、17 也一定可以沿用原方案；若容量 10 都装不完，容量 9 更不可能装完。于是容量区间上会出现 false 到 true 的分界。

带数字例子：weights=[1,2,3,4,5]，D=3。容量 5 需要 [1,2] [3] [4] [5] 共 4 天，不可行；容量 6 需要 [1,2,3] [4] [5] 共 3 天，可行；容量 7 也可行。目标就是找最小可行容量 6。

capacity: 4  5  6  7  8 ...
can:      F  F  T  T  T ...

记忆钩子：二分容量时，容量越大约束越宽；找的就是“刚刚够用”的那条线。

三、上下界怎么从题意推出

下界必须是最大单个包裹重量，因为船容量小于某个包裹时，这个包裹任何一天都装不上。上界是所有包裹重量总和，因为容量等于总和时，一天就能全部运完，必然可行。这个区间一定覆盖答案。

例如 weights=[3,2,2,4,1,4]，最大单件是 4，总和是 16，所以答案只可能在 [4,16]。如果把下界写成 1，虽然也可能算出答案，但会浪费搜索轮次，并且没有体现对题意的理解。

lo = max(weights)
hi = sum(weights)

四、可行性检查为什么用贪心装满当前天

在给定容量 cap 时，最少天数的策略是当天能装就装，装不下才开新一天。因为包裹顺序固定，把一个能装的包裹推迟到下一天不会让当前天更好，只会减少后续天的容量余量。因此“尽量装满当前天”是安全的。

以 cap=6、[3,2,2,4,1,4] 为例，第一天装 3 和 2 后剩 1，下一个 2 放不下，于是开新天。若你第一天只装 3，把 2 留到后面，后续并不会更少天，反而可能更差。这就是可行性模拟中贪心的依据。

day1: 3 + 2 = 5
day2: 2 + 4 = 6
day3: 1 + 4 = 5

五、为什么找的是左边界

题目要最小容量，而所有可行容量形成一个右侧区间。二分时如果 mid 可行，不能直接返回，因为左边可能还有更小可行容量；要把 hi 收到 mid。如果 mid 不可行，说明容量不够，lo = mid + 1。

循环使用 while (lo < hi) 时，结束后 lo == hi，这个点就是第一个 true。这个模板和 Koko 吃香蕉完全同构，只是速度换成容量，小时数换成天数。

can(mid) true  -> hi = mid
can(mid) false -> lo = mid + 1

六、复杂度和工程视角

每次可行性检查需要扫一遍包裹，O(n)。二分容量范围从 maxWeight 到 sumWeight，所以总复杂度是 O(n log(sum-max))，通常简写为 O(n log S)。空间是 O(1)，不算输入。

工程上这类题也很像容量规划：给定 SLA 天数，求最小机器容量、带宽、批处理吞吐。关键不是模拟所有方案，而是找到一个单调资源参数，再写一个可靠的可行性检查函数。面试中能把它抽象成“最小可行资源”会更稳。

资源类题	二分对象	可行性
运送包裹	船容量	天数不超过 D
机器吞吐	每秒处理量	延迟不超过 SLA
分割数组	最大段和	段数不超过 m

七、常见误区与追问

误区：可以先排序包裹。 题目要求按原顺序运输，排序会改变问题。
误区：容量下界可以从 1 开始。 小于最大单件重量的容量一定不可行，正确下界是 max(weights)。
误区：mid 可行就返回。 题目要求最小可行容量，要继续寻找左边界。
追问：为什么当前天能装就装是正确的？ 顺序固定时，推迟能装的包裹不会减少后续压力，只会浪费当前天容量。
追问：如果包裹顺序可以任意调整怎么办？ 问题会变成更复杂的装箱/调度问题，当前线性贪心不再成立。
追问：复杂度如何估算？ 每轮 O(n) 模拟，轮数是容量范围的对数，因此 O(n log S)。

八、加强记忆

运包题的关键链条是“容量越大，天数越少，所以可二分”。边界从题意推：最小不能小于最大包裹，最大不超过总重量。can(cap) 按顺序贪心装，能装就装，装不下开新天。可行就往左找，不可行就往右扩，最终得到刚好够用的最小容量。

简化版

详细版