二分答案

先证明可行性随答案单调变化

以包裹按原顺序分天运输为例，容量 C 越大，需要的天数不会增加，因此“能否在 D 天内运完”是前假后真的条件。

容量下界为最大单件重量，上界为总重量。判断时依次装包裹，超过容量就开始新的一天；贪心让每天尽可能多装连续包裹，在固定容量下得到最少天数。

在整数容量范围内二分第一个可行值，若一次判定 O(n)、答案范围大小 V，总时间 O(n log V)。没有单调性的判定不能靠二分得到可靠答案。

最小运货容量与极端边界

例1：两天运完包裹的最小容量

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
    vector<int> w = {3, 2, 2, 4, 1};
    long long l = *max_element(w.begin(), w.end());
    long long r = accumulate(w.begin(), w.end(), 0LL);
    auto ok = [&](long long cap) {
        int days = 1; long long used = 0;
        for (int x : w) {
            if (used + x > cap) { ++days; used = 0; }
            used += x;
        }
        return days <= 2;
    };
    while (l < r) {
        long long m = l + (r - l) / 2;
        if (ok(m)) r = m; else l = m + 1;
    }
    cout << l << endl;
}

输出 7。容量 6 要三天，容量 7 可分为 [3,2,2] 和 [4,1]，故最小可行值是 7。

例2：上下界与极端天数

若只能用 1 天，容量至少等于总重量；若允许每件单独一天，最小容量等于最大单件重量。

这两个边界可用来检查程序。下界设为 0 却未处理“单件超过容量”，会让判定函数误报可行。

提示

• 先说明答案变大时可行性如何变化，再选择二分更新方向。
• 本例不允许重排包裹，若改变顺序就变成另一道问题。
• 总重量和累计载重可能溢出 int，使用更宽的整数。

先修知识

• 二分查找

技术参考

• C++ working draft: binary search

范围说明

本站讲解由 InfoCode 编写，不是官方考纲；参考级别是本站映射，不代表官方等级、认证或参赛资格。练习记录不等于掌握或资格。

参考级别：GESP 5 级（本站映射）

查看赛事关系与路径