1011. 在 D 天内送达包裹的能力：「二分答案模板」，最小化最大值之类的问题，考虑二分答案.md

题目简述：

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

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

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

提示：

• 1 <= days <= weights.length <= 5 * 10^4
• 1 <= weights[i] <= 500

题目链接：1011. 在 D 天内送达包裹的能力

二分答案

最小化最大值之类的问题，通常考虑「二分答案」，尽管我更愿意将其称之为「值域二分」。

例如，在本问题中，船的运载能力越大，越容易在 days 天内运载完所有包裹，而我们要计算的是船的最小运力。

类似的典型问题还有：

• 410. 分割数组的最大值
• 875. 爱吃香蕉的珂珂

思路

必须要看破本问题「最小化最大值」的本质，不然应该是很难想出来的。只要第一眼就看穿了本问题背后的「二分答案」，那么算法就是水到渠成的。

此外，注意到所有包裹的重量均为正整数，对于在同一天内被运载的货物，其总重量会随着货物数量的增加而严格递增，因此此处存在单调性。

最后，本问题中需要被「最小化」的「单调函数」是「线性扫描 & 贪心计数」，这告诉了我们如何设计 canShip 方法。实际上410. 分割数组的最大值与875. 爱吃香蕉的珂珂也是这样的，因此这三个问题实际上完全是相同逻辑。

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int low = 0;
        int high = 0;
        for (int weight : weights) high += weight;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (!canShip(weights, days, mid)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }

    /**
     * payload: 人为设定的船最大运载能力，贪心计数时以该值为上界
     */
    private boolean canShip(int[] weights, int days, int payload) {
        int count = 1;   // 运载所有货物所需天数
        int amount = 0;  // 一天内运载的货物总质量
        for (int weight : weights) {
            if (amount + weight <= payload) {
                amount += weight;
            } else if (weight > payload) {
                return false;
            } else {
                count++;
                if (count > days) return false;
                amount = weight;
            }
        }

        return true;
    }
}