RootStack

C++ 算法技巧 — 二分答案 (Binary Answer)

7分钟阅读

章节概述

二分答案是将答案所在的范围不断二分，通过判定中间值是否可行来逼近最优解。
是”二分查找”在高维问题上的推广。

核心原理

1. 数学基础

二分答案的本质是求以下两类问题的临界值：

  • 最小化最大值: 答案越小越难满足，求最小的可行值
  • 最大化最小值: 答案越大越难满足，求最大的可行值

2. 单调性要求

check(mid) 关于 mid 必须具有单调性：

  • 若 mid 可行，则所有 ≥ mid 的值都可行（最小化问题）
  • 若 mid 可行，则所有 ≤ mid 的值都可行（最大化问题）

3. 通用框架

l = 答案下界, r = 答案上界
while (l <= r):
    mid = (l + r) / 2
    if check(mid):
        ans = mid
        if 最小化: r = mid - 1
        if 最大化: l = mid + 1
    else:
        if 最小化: l = mid + 1
        if 最大化: r = mid - 1

时间复杂度: O(log(值域) × check复杂度)

4. 典型模式

问题类型二分对象check内容
数列分段最大段和上限贪心分段，看段数是否 ≤ M
跳石头最短跳跃距离模拟跳，看移除石头数是否 ≤ M
路标设置空旷指数计算需添加路标数是否 ≤ K

关键数据结构

P1182 数列分段 Section II

题目: 给定 N 个正整数数列 A，要求将其划分为连续的 M 段，使得各段和的最大值尽可能小。求这个最小化的最大段和。

思路: 二分答案 mid = 最大段和的上限。check 函数：贪心地从前往后分段，每段总和不超过 mid，
如果需要的段数 ≤ M 则 mid 可行。

#include <iostream>
using namespace std;
int a[100005];
int n, m;
 
bool check(int mid) {
    int cnt = 1, sum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > mid) return false;
        if (sum + a[i] > mid) {
            cnt++;
            sum = a[i];
        } else {
            sum += a[i];
        }
    }
    return cnt <= m;
}
 
int main() {
    cin >> n >> m;
    int l = 0, r = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        l = max(l, a[i]);
        r += a[i];
    }
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

P2678 [NOIP2015 提高组] 跳石头

题目: 起点到终点长度 L，中间有 N 块石头位置为 d_i。需要移走 M 块石头，使得最短跳跃距离尽可能大。求满足条件的最短跳跃距离的最大值。

思路: 二分最短跳跃距离 mid，check 函数：从头开始模拟跳过石头，看移除的石头数是否 ≤ M。

#include <iostream>
using namespace std;
int d[50005];
int L, n, m;
 
bool check(int mid) {
    int cnt = 0, pre = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (d[i] - pre < mid) cnt++;
        else pre = d[i];
    }
    return cnt <= m;
}
 
int main() {
    cin >> L >> n >> m;
    for (int i = 1; i <= n; i++) cin >> d[i];
    d[n + 1] = L;
    int l = 1, r = L, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

P3853 [TJOI2007] 路标设置

题目: 一条公路长度 L，起点已有一些路标。相邻路标之间距离不能超过一个”空旷指数” K。可能需要添加一些路标，求需要添加的最少路标数，使得空旷指数最小化，求该最小空旷指数。

思路: 二分空旷指数 mid，check 函数：遍历相邻路标，计算需要添加的路标数是否 ≤ K。

#include <iostream>
using namespace std;
int a[100005];
int L, n, k;
 
bool check(int mid) {
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        int gap = a[i] - a[i - 1];
        if (gap > mid)
            cnt += (gap - 1) / mid;
    }
    return cnt <= k;
}
 
int main() {
    cin >> L >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    int l = 1, r = L, ans = L;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

推荐练习题（洛谷）

相关技巧

  • 二分查找: 二分答案的 check 函数本质是对确定的答案做判定
  • 贪心: 二分答案常与贪心配合，贪心判定给定 mid 是否可行
  • 前缀和: check 函数中快速计算区间信息

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |

关系图谱

反向链接