普通二分查找在有序数组里找位置；二分答案则不直接构造最优方案，而是反复询问：“答案至少达到 x，能做到吗？”只要可行性随 x 单调变化，就能在答案空间里找到最后一个可行值。

本文选择三道 Codeforces 题，分别练习中位数提升、共享资源分配和配方生产。它们的题面不同，但代码骨架几乎一致：定义 can(x)、找到可靠上界、维护一个可行点和一个不可行点。

1. 二分答案的核心不是 while 循环

假设要最大化一个整数答案，并且：

1
can(x) = true  表示答案至少可以达到 x

如果 can(x) 为真能推出所有更小值也为真，那么答案轴具有如下结构：

1
2
3
true true true ... true | false false ... false
                         ↑
                    最大可行值

真正需要证明的是两件事：

  1. can(x) 是否准确描述“至少达到 x”；
  2. can(x) 是否单调。

若这两点不成立，再漂亮的二分模板也只是在快速得到错误答案。

2. 一个不容易写错的边界约定

本文统一维护：

  • low：已知可行；
  • high：已知不可行；
  • 搜索区间为 (low, high)。
1
2
3
4
5
6
7
8
9
while (low + 1 < high) {
    long long middle = low + (high - low) / 2;
    if (can(middle)) {
        low = middle;
    } else {
        high = middle;
    }
}
cout << low << '\n';

循环结束时二者相邻，low 就是最后一个可行答案。这套写法的重点不是记忆，而是让变量语义在每次更新后保持不变。

3. 1201C · Maximum Median：提升排序后的右半段

查看官方题目

数组长度为奇数，每次操作可以让任一元素加一，最多操作 k 次。排序后，中位数位于 n / 2。若希望中位数至少为 target，不仅要提升当前中位数，还要让它右侧所有低于 target 的元素一起达到该值：

1
cost(target) = Σ max(0, target - a[i]),  i = n/2 ... n-1

左半段不会阻碍中位数提高，因此不用花预算修改。target 越大，最低成本不会下降，可行性满足单调性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;

    vector<long long> values(n);
    for (long long& value : values) cin >> value;
    sort(values.begin(), values.end());

    int median = n / 2;
    auto can = [&](long long target) {
        long long cost = 0;
        for (int i = median; i < n; ++i) {
            if (values[i] < target) {
                cost += target - values[i];
                if (cost > k) return false;
            }
        }
        return true;
    };

    long long low = values[median];
    long long high = values[median] + k + 1;
    while (low + 1 < high) {
        long long middle = low + (high - low) / 2;
        if (can(middle)) low = middle;
        else high = middle;
    }

    cout << low << '\n';
}

上界 values[median] + k + 1 一定不可行，因为即使只提升一个元素，也已经需要超过全部预算。时间复杂度为 O(n log n + n log k)。

4. 670D1 · Magic Powder - 1：把通用资源补到缺口

查看官方题目

制作一个饼干需要第 i 种原料 need[i] 克，现有 have[i] 克，另有 k 克魔法粉可以变成任意原料。若制作 cookies 个，所需粉末为：

1
powder(cookies) = Σ max(0, need[i] × cookies - have[i])

只要总缺口不超过 k 就可行。目标数量增加时，每种原料的缺口都不会减少，因此可以二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long powder;
    cin >> n >> powder;

    vector<long long> need(n), have(n);
    for (long long& value : need) cin >> value;
    for (long long& value : have) cin >> value;

    auto can = [&](long long cookies) {
        long long missing = 0;
        for (int i = 0; i < n; ++i) {
            long long required = need[i] * cookies;
            if (required > have[i]) {
                missing += required - have[i];
                if (missing > powder) return false;
            }
        }
        return true;
    };

    long long low = 0;
    long long high = 2'000'000'001LL;
    while (low + 1 < high) {
        long long middle = low + (high - low) / 2;
        if (can(middle)) low = middle;
        else high = middle;
    }

    cout << low << '\n';
}

这里使用宽松但安全的固定上界。若无法从约束快速推出上界，也可以从 1 开始不断翻倍，直到第一次不可行。

5. 371C · Hamburgers：库存之外还要计算购买成本

查看官方题目

配方字符串由 B、S、C 构成。先统计一个汉堡分别需要多少面包、香肠和奶酪。制作 count 个时，超过库存的部分需要按单价购买：

1
cost(count) = Σ max(0, recipe[i] × count - stock[i]) × price[i]

当 count 增大，购买成本不会下降。由于资金上限达到 10^12，中间乘法使用 __int128，避免尚未比较预算就发生 long long 溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string recipeText;
    cin >> recipeText;

    array<long long, 3> recipe{0, 0, 0};
    for (char ingredient : recipeText) {
        int index = ingredient == 'B' ? 0 : ingredient == 'S' ? 1 : 2;
        ++recipe[index];
    }

    array<long long, 3> stock, price;
    for (long long& value : stock) cin >> value;
    for (long long& value : price) cin >> value;

    long long money;
    cin >> money;

    auto can = [&](long long count) {
        __int128 cost = 0;
        for (int i = 0; i < 3; ++i) {
            long long missing = max(0LL, recipe[i] * count - stock[i]);
            cost += static_cast<__int128>(missing) * price[i];
            if (cost > money) return false;
        }
        return true;
    };

    long long low = 0;
    long long high = 1;
    while (can(high)) high *= 2;

    while (low + 1 < high) {
        long long middle = low + (high - low) / 2;
        if (can(middle)) low = middle;
        else high = middle;
    }

    cout << low << '\n';
}

指数扩展上界避免了“凭感觉写一个很大的数”。在本题约束下答案远小于 long long 上限，翻倍过程安全；一般题目仍应先根据约束判断翻倍是否可能溢出。

6. 三道题的建模对照

题目 猜测的答案 can(x) 的最低成本 单调性的来源
1201C 中位数至少为 x 右半段补到 x 的增量 目标越高，补齐量不减
670D1 至少做 x 个饼干 所有原料的总缺口 数量越多，缺口不减
371C 至少做 x 个汉堡 库存外原料的购买费用 数量越多，费用不减

7. 提交前的边界检查

  • low 和 high 是否真的分别满足可行、不可行；
  • 求最大值时最后输出的是 low 还是 high；
  • 成本累加能否提前在超过预算时返回；
  • middle 是否用 low + (high - low) / 2 避免加法溢出；
  • 乘法是否先在足够宽的整数类型中完成；
  • can(x) 是否只判断可行性，没有偷偷依赖二分过程外的可变状态。

如果题目只是从有序数组中找第一个位置，可先复习 Codeforces 序列优化四题 中的 lower_bound 与 upper_bound。当目标从“找位置”变成“最大化一个满足约束的数值”，再使用本文的答案二分框架。

官方来源