信息学竞赛 C++ 教材

Appearance

第 47 章 二分答案——从查找值到查找可行域 ​

🏗️ 前情回顾：第 46 章你学会了在有序数组中二分查找一个具体的值。但二分的思想远不止于此——如果把"值"扩展成"问题的答案"，二分就能用来猜答案。这就是本章的主角——二分答案，信息学竞赛中的高频考点。

🎯 本章目标 ​

学完这一章，你能：

  • 理解二分答案的核心思想：猜一个答案，验证是否可行
  • 掌握 check 函数的设计——这是二分答案最关键的技能
  • 写出整数二分答案的标准模板
  • 处理浮点二分答案（精度控制）
  • 解决砍树、木材加工、跳石头等经典问题
  • 看到"最大值最小"或"最小值最大"就条件反射想到二分答案

📖 故事引入 ​

你在洗澡。水太冷了，你往热水那边拧一点；太烫了，又往冷水那边拧一点。拧来拧去，终于调到一个刚刚好的温度。

这个过程你不陌生吧？其实你就在做二分答案——在一个连续的范围内，不断调整，找一个"刚刚好"的平衡点。

再想一个问题：有一排 n 棵树，高度分别是 h₁, h₂, ..., hₙ。你需要砍下总长度至少为 M 的木材。你的电锯可以设定一个高度 H，所有高于 H 的部分都会被砍下来。你希望 H 尽可能大（少砍点树），但必须满足砍下的总长度 ≥ M。

H 能取多少？你也许想：从 0 开始试，H=0 全部砍下肯定够，H=1 再试试……但这太低效了。H 最大可以是最高树的高度（比如 10^9），一个个试肯定超时。

换个思路：如果 H 的值有一个"单调性"——H 越小，砍下的木材越多——那么你可以二分 H！猜一个 H，计算砍下的总长度，够就试试更大的 H，不够就减小 H。

这就是二分答案：把"查找一个值"变成"查找一个满足条件的临界点"。

🧱 知识讲解 ​

47.1 二分答案的适用条件 ​

二分答案不是万能的。问题必须满足：

  1. 答案具有单调性：如果某个值可行，那么比它"更好"的一侧也都可行（或都不可行）
  2. 存在一个临界点：一侧满住条件，另一侧不满足
  3. check 函数高效：给定一个候选答案，能在合理时间内判断是否可行

🎯 看到题目中有"最大值最小"或"最小值最大"，99% 就是二分答案！

47.2 check 函数：二分答案的灵魂 ​

二分答案的框架和二分查找一样，但关键不在二分本身，而在 check(mid)——判断 mid 这个答案是否可行。

cpp
bool check(int mid) {
    // 根据题意，判断 mid 作为答案是否可行
    // 返回 true 表示可行，false 表示不可行
}

47.3 整数二分答案模板 ​

场景一：求"最大的可行值"（最大值最大化）

cpp
int l = 最小可能值, r = 最大可能值, ans = l;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;       // 记录当前可行答案
        l = mid + 1;     // 尝试更大的
    } else {
        r = mid - 1;     // mid 不行，只能更小
    }
}
cout << ans;

场景二：求"最小的可行值"（最小值最小化）

cpp
int l = 最小可能值, r = 最大可能值, ans = r;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;       // 记录当前可行答案
        r = mid - 1;     // 尝试更小的
    } else {
        l = mid + 1;     // mid 不行，只能更大
    }
}
cout << ans;

🧠 关键区别：可行时往哪边收缩。求最大值 → 可行时 l = mid+1；求最小值 → 可行时 r = mid-1。

47.4 经典题一：砍树 ​

问题：n 棵树高度 a₁...aₙ，锯片高度 H，获得木材 = Σ max(0, aᵢ - H)。需要至少 M 米木材，求 H 最大能设多少。

cpp
int n, m;
int a[1000005];

bool check(int H) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > H) sum += a[i] - H;
    }
    return sum >= m;     // 砍下的木材够 m 米
}

int main() {
    cin >> n >> m;
    int maxH = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        maxH = max(maxH, a[i]);
    }
    int l = 0, r = maxH, ans = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;      // 可行，试试能不能更高
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

47.5 经典题二：跳石头（最小值最大化） ​

问题：一条直线上有 n 块石头，距起点距离为 d₁...dₙ。要去掉 m 块石头，使得相邻石头之间的最小距离尽可能大。求这个最大化的最小距离。

思路：二分"最小距离"mid。check(mid) 判断：能否通过去掉 ≤ m 块石头，使得任意相邻石头间距 ≥ mid？

check 策略：从起点开始贪心——如果当前石头和上一块保留石头的距离 < mid，就搬走当前石头；否则保留它。统计搬走的数量，判断是否 ≤ m。

cpp
bool check(int mid) {
    int removed = 0;
    int last = 0;  // 上一块保留石头的位置（起点为 0）
    for (int i = 1; i <= n; i++) {
        if (d[i] - last < mid) {
            removed++;         // 距离不够，搬走
        } else {
            last = d[i];       // 保留
        }
    }
    // 别忘了终点 L：
    if (L - last < mid) removed++;
    return removed <= m;
}
// 二分求最大化的最小距离

🎯 "最小值最大"→ 二分 mid → check(mid) 用贪心判断 → 可行就往大里试。

47.6 浮点二分答案 ​

如果答案不是整数而是浮点数（比如"求满足某个精度的 x"），写法基本一样，只是边界处理不同：

cpp
double l = 0, r = 1e9;
for (int i = 0; i < 100; i++) {   // 迭代 100 次，精度足够
    double mid = (l + r) / 2;
    if (check(mid))
        l = mid;        // 注意：浮点二分不需要 ±1
    else
        r = mid;
}
cout << fixed << setprecision(6) << l;

⚠️ 浮点二分不要用 while (r - l > eps)，固定迭代次数（如 60~100 次）更安全，避免精度死循环。

✋ 动手试试 ​

试试 1：实现砍树问题。输入 n=4, m=7, 高度为 20 15 10 17。手工算一下：H 分别取 15, 16, 17, 14 时各砍下多少？用二分程序验证。

试试 2：实现跳石头问题简化版。L=25, n=5, m=2, 石头位置：2, 11, 14, 17, 21。思考：搬走哪两块能使最小间距最大？最小间距最大能到多少？

试试 3：浮点二分练习——求 sqrt(2) 的近似值（不调用 sqrt 函数）。二分搜索区间 [0, 2]，check(mid) 判断 mid*mid 是否 ≤ 2。迭代 60 次，输出保留 10 位小数。

⚠️ 容易犯的错 ​

错 1：忘了单调性就二分 ​

❌ 问题没有单调性却硬套二分 → 答案错误

✅ 二分的 check 结果必须随 mid 单调变化

错 2：check 函数写错了逻辑 ​

❌ return sum >= m; 和 return sum <= m; 搞反

✅ 仔细读题，明确"可行"是什么意思

错 3：二分边界设错了 ​

❌ 砍树问题中 r = 0 或忘了设 ans 初始值

✅ l 和 r 覆盖答案的所有可能范围，ans 初始为不可行的值

错 4：浮点二分用 while(r-l > eps) ​

❌ while (r - l > 1e-8) → eps 太小可能死循环

✅ 固定迭代次数：for (int i = 0; i < 80; i++)

错5：check 内使用 long long 的范围 ​

❌ 砍树问题中用 int sum 存 Σ(aᵢ-H)，可能溢出

✅ 用 long long 存累加结果

📝 练习 ​

基础题 ​

1. 选择题

（1）二分答案适用的条件是？
A. 数据有序   B. 答案具有单调性   C. n ≤ 100   D. 必须整数

（2）"求最大化的最小值"时，check 可行后应该？
A. l = mid - 1   B. l = mid + 1   C. r = mid   D. 直接返回 mid

（3）浮点二分推荐用什么方式控制终止？
A. while(l < r)   B. while(r-l > 1e-12)   C. 固定迭代次数   D. do-while

2. 填空题

（1）二分答案的两大要素：答案具有____、____函数高效。

（2）求最大值时，check 可行则 l = ____ + 1；求最小值时，check 可行则 r = ____ - 1。

（3）砍树问题中砍下的总木材 = Σ max(0, ____ - ____)。

提高题 ​

3. 编程题 — 木材加工

有 n 根原木，长度分别为 L₁...Lₙ。需要切成等长的 k 段小木料。求小木料的最大长度。（每段原木可以切成若干段，不能拼接。）

check(mid)：判断 ∑ floor(Lᵢ / mid) ≥ k。

4. 编程题 — 数列分段

给定 n 个正整数，分成连续的 m 段，使得每段和的最大值最小。求这个最小值。

提示：二分"每段和的最大值"mid。check(mid) 贪心分段，尽量凑满 mid 再分段，看最终段数是否 ≤ m。

挑战题 ​

5. 编程题 — 电缆切割

有 n 条电缆，长度分别为 a₁...aₙ（浮点数，单位米），精确到厘米。需要切成 k 条等长的电缆。求能切出的最大长度（精确到厘米，即保留两位小数）。

提示：把输入 ×100 转成整数（厘米），整数二分，输出时 ÷100.0。

🧠 本章小结 ​

二分答案 = 猜答案 + 验证

适用条件：
  · 答案具有单调性
  · check(mid) 能高效判断是否可行

两大模板：
  求最大值 → check 可行时 l = mid+1（往大试）
  求最小值 → check 可行时 r = mid-1（往小试）

check 函数是灵魂：给定 mid，判断是否可行

经典问题：
  砍树（最大值）   → 锯片高度 H 最大
  跳石头（最小值） → 最小间距最大
  木材加工         → 等长小段最大长度

浮点二分：固定迭代次数（60~100 次），不要用 while(r-l>eps)

关键信号词："最大值最小" / "最小值最大" → 二分答案！

📝 配套练习 ​

共9题。二分答案是M7题量最大的章——从砍树模板→贪心check→浮点二分→差分check→前缀和check，check函数设计能力逐级增强。。★核心（课堂必做） ◆拓展（课后练习） ★★★挑战（选做）

级别题号链接覆盖知识点
★ 核心luogu-P1873https://hydro.ac/p/luogu-P1873二分答案、砍树、check=m锯下≥M
◆ 拓展luogu-P2440https://hydro.ac/p/luogu-P2440二分答案、木材加工、check=段数≥k
◆ 拓展luogu-P2678https://hydro.ac/p/luogu-P2678二分答案+贪心check、跳石头
◆ 拓展luogu-P1182https://hydro.ac/p/luogu-P1182二分答案+贪心分段、数列分段
◆ 拓展luogu-P1163https://hydro.ac/p/luogu-P1163浮点二分、贷款利率
◆ 拓展luogu-P1577https://hydro.ac/p/luogu-P1577浮点二分、切绳子
◆ 拓展luogu-P1083https://hydro.ac/p/luogu-P1083二分答案+差分check、借教室
◆ 拓展luogu-P1314https://hydro.ac/p/luogu-P1314二分答案+前缀和、质量检测
★★★ 挑战luogu-P4343https://hydro.ac/p/luogu-P4343二分答案、自动刷题机

💡 练习建议：先完成 2 道★核心题，确保掌握本章基本方法；再完成 7 道◆拓展题，覆盖不同变式和细节；★★★挑战题建议在完成拓展题后再做，涉及多知识点综合。

配套练习 ​

共9题。二分答案是M7题量最大的章——从砍树模板→贪心check→浮点二分→差分check→前缀和check，check函数设计能力逐级增强。★核心（课堂必做） · ◆拓展（课后练习） · ★★★挑战（选做）

级别题号链接覆盖知识点
★ 核心luogu-P1873https://hydro.ac/p/luogu-P1873二分答案、砍树、check=m锯下≥M
◆ 拓展luogu-P2440https://hydro.ac/p/luogu-P2440二分答案、木材加工、check=段数≥k
◆ 拓展luogu-P2678https://hydro.ac/p/luogu-P2678二分答案+贪心check、跳石头
◆ 拓展luogu-P1182https://hydro.ac/p/luogu-P1182二分答案+贪心分段、数列分段
◆ 拓展luogu-P1163https://hydro.ac/p/luogu-P1163浮点二分、贷款利率
◆ 拓展luogu-P1577https://hydro.ac/p/luogu-P1577浮点二分、切绳子
◆ 拓展luogu-P1083https://hydro.ac/p/luogu-P1083二分答案+差分check、借教室
◆ 拓展luogu-P1314https://hydro.ac/p/luogu-P1314二分答案+前缀和、质量检测
★★★ 挑战luogu-P4343https://hydro.ac/p/luogu-P4343二分答案、自动刷题机

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 7 道◆拓展题，覆盖不同变式和细节；★★★挑战题建议在完成拓展题后再做，涉及多知识点综合。

自查清单：

  • [ ] 我理解二分答案和二分查找的区别
  • [ ] 我能识别"二分答案"的信号词
  • [ ] 我能设计 check 函数
  • [ ] 我能写出整数二分答案的正确模板
  • [ ] 我知道浮点二分要用固定迭代次数
  • [ ] 我能解决砍树和木材加工这类经典问题

🚀 下章预告：二分答案让你在"可行域"中高效搜索。但有些问题没有单调性，不能二分——比如"最优装载"，比如"活动选择"。这时你需要另一种智慧：每步都选当下看起来最好的。这就是第 48 章——贪心算法。准备迎接最"聪明"也最容易翻车的算法范式！🎯