📖 第 3.5b 章：二分答案

⏱ 预计阅读时间：40 分钟 | 难度：🟡 中等

前置条件

在学习本章之前，请确保你已掌握：

数组与循环（第 2.2 章）
lower_bound / upper_bound 的基本用法（第 3.3 章）

🎯 学习目标

学完本章后，你将能够：

识别「可以用二分答案」的题目特征（三要素）
区分「找第一个满足条件」和「找最后一个满足条件」两种模板
设计正确的 check 函数
处理浮点二分和三分法求极值
避免整数二分中的边界死循环

3.5b.1 什么是二分答案？

从枚举到二分

考虑这个问题：

你有 N 根木头，每根长度不同。需要切出 K 根长度相等（都为 x）的木棍，问 x 的最大值是多少？

朴素思路： 枚举所有可能的 x，检查是否满足条件。

若 x 能切出 ≥ K 根 → 合法
若 x 太大，切不出 → 不合法

这需要 O(10^9) 次检查，太慢了。

二分答案的洞察：
如果 x = 5 可以切出 ≥ K 根，那 x = 4 肯定也可以（每根切的数量只会更多）。
也就是说，满足条件的 x 构成一个连续区间 [0, 某个上界]。
我们可以对这个区间二分，每次检查中点是否合法。

3.5b.2 二分答案的三要素

使用二分答案必须满足以下三个条件：

条件	说明	验证方法
① 答案在固定区间内	能确定答案的上下界	分析题目数据范围
② check 函数易于实现	给定一个答案值，能快速判断是否合法	通常用贪心或 O(N) 扫描
③ 单调性	若 x 合法，则更小（或更大）的值也合法	手动举反例验证

单调性的两种形式

形式 1：「最大值最小化」
合法区间在左侧：0 0 0 [1 1 1 1 1]
→ 找最后一个合法值（最右侧的 1）

形式 2：「最小值最大化」
合法区间在右侧：[1 1 1 1 1] 0 0 0
→ 找第一个合法值（最左侧的 1）

3.5b.3 整数二分模板

模板 A：找满足条件的最大值（最大化）

📄 查看代码：模板 A：找满足条件的最大值（最大化）

// 找最大的 x，使 check(x) == true
// 前提：check 形如 [true...true, false...false]

bool check(int x) {
    // 判断 x 是否满足条件
    // ...
}

int binary_search_max() {
    int lo = 可能的最小值;
    int hi = 可能的最大值 + 1;  // hi 是第一个不合法的值
    
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;  // 防溢出写法
        if (check(mid))
            lo = mid;   // mid 合法，尝试更大的
        else
            hi = mid;   // mid 不合法，答案在左侧
    }
    
    return lo;  // lo 是最大的合法值
}

模板 B：找满足条件的最小值（最小化）

📄 查看代码：模板 B：找满足条件的最小值（最小化）

// 找最小的 x，使 check(x) == true
// 前提：check 形如 [false...false, true...true]

int binary_search_min() {
    int lo = 可能的最小值 - 1;  // lo 是第一个不合法的值
    int hi = 可能的最大值;
    
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid))
            hi = mid;   // mid 合法，尝试更小的
        else
            lo = mid;   // mid 不合法，答案在右侧
    }
    
    return hi;  // hi 是最小的合法值
}

为什么用 `lo + 1 < hi` 而不是 `lo < hi`？

📄 查看代码：为什么用 lo + 1 < hi 而不是 lo < hi？

终止条件分析：
  循环条件 lo + 1 < hi，即 lo 和 hi 不相邻时继续
  
  终止时：lo + 1 == hi
  此时 lo 是最大的合法值，hi 是最小的不合法值
  
  若用 lo < hi，则 mid = (lo+hi)/2 = lo，会死循环！
  
示例：lo=4, hi=5
  mid = 4 + (5-4)/2 = 4
  若 check(4)=true，lo = mid = 4（没有变化！死循环）

3.5b.4 完整例题：切木头

有 N 根木头，长度为 a[1..N]，需要切出 K 根长度为 H 的木棍。
每切一根，从长度 L > H 的木头中截取一段 H，剩余部分保留。
求 H 的最大值（整数）。

分析

答案范围： H ∈ [1, max(a)]
check(H)： 扫描所有木头，统计能切出多少根长 H 的木棍，是否 ≥ K
单调性： H 越大，切出的根数越少（check 从 true 变 false），满足最大化模式

📄 C++ 完整代码

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> a;

// 检查高度 H 能否切出 >= k 根
bool check(long long H) {
    long long total = 0;
    for (int x : a) {
        total += x / H;  // 每根木头能切出几段
    }
    return total >= k;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    for (int& x : a) cin >> x;
    
    long long lo = 1, hi = *max_element(a.begin(), a.end()) + 1;
    
    while (lo + 1 < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid))
            lo = mid;   // 可以切出够多，尝试更高
        else
            hi = mid;   // 切得太短，上界降低
    }
    
    cout << lo << endl;  // 最大的合法高度
    return 0;
}

追踪示例：
木头长度 = [8, 5, 3, 2]，K = 5

lo=1, hi=9

mid=5：check(5) = 8/5+5/5+3/5+2/5 = 1+1+0+0 = 2 < 5 → false，hi=5
mid=3：check(3) = 8/3+5/3+3/3+2/3 = 2+1+1+0 = 4 < 5 → false，hi=3
mid=2：check(2) = 8/2+5/2+3/2+2/2 = 4+2+1+1 = 8 >= 5 → true，lo=2

lo+1 = 3 = hi，循环结束

答案：lo = 2

3.5b.5 例题：最大化最小值（安置奶牛）

USACO 经典题：N 个牛栏位于 1D 数轴上（坐标已知），放 C 头奶牛，
使得相邻奶牛之间的最小距离最大，求这个最大值。

分析

答案范围： [1, max_coord - min_coord]
check(D)： 贪心地从左到右放置奶牛，若相邻奶牛距离 ≥ D，则放下一头
单调性： D 越大越难满足（最小化模式的反向）

📄 C++ 完整代码

#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> pos;

// 检查：最小距离至少为 D，能否放 >= c 头奶牛？
bool check(int D) {
    int cows = 1;          // 第一头放在最左边
    int last = pos[0];     // 上一头奶牛的位置
    
    for (int i = 1; i < n; i++) {
        if (pos[i] - last >= D) {
            // 距离足够，放一头奶牛
            cows++;
            last = pos[i];
            if (cows >= c) return true;
        }
    }
    return cows >= c;
}

int main() {
    cin >> n >> c;
    pos.resize(n);
    for (int& x : pos) cin >> x;
    sort(pos.begin(), pos.end());   // 按位置排序
    
    int lo = 0, hi = pos.back() - pos.front() + 1;
    
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid))
            lo = mid;   // 间距 mid 可行，尝试更大
        else
            hi = mid;
    }
    
    cout << lo << endl;
    return 0;
}

3.5b.6 浮点二分

当答案是实数时，用「循环足够多次」代替「两点相邻」：

// 浮点二分（精度 1e-7）
double lo = 0.0, hi = 1e9;
for (int iter = 0; iter < 100; iter++) {  // 100次足够精确到 1e-30
    double mid = (lo + hi) / 2.0;
    if (check(mid))
        lo = mid;
    else
        hi = mid;
}
// (lo + hi) / 2 即为答案，精度约 1e-30

也可以用 while (hi - lo > 1e-7) 作终止条件，但循环次数不固定（约 50 次）。

注意： 浮点比较需留意精度，check 中不要用 ==。

3.5b.7 三分法（求单峰函数极值）

当需要求「单峰函数」的最大/最小值时，使用三分法：

单峰函数： 存在一个极值点，左侧单调递增，右侧单调递减（或相反）。

f(x):  2 4 7 9 8 6 3
           ↑
          极值点（峰值 = 9）

三分法思路

在区间 [lo, hi] 中取两个三等分点 lmid 和 rmid：

若 f(lmid) < f(rmid)：极值点在 lmid 右侧，lo = lmid
若 f(lmid) > f(rmid)：极值点在 rmid 左侧，hi = rmid

📄 C++ 完整代码

// 三分法（浮点版，求单峰函数最大值点）
double ternary_search(double lo, double hi) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3.0;
        double m2 = hi - (hi - lo) / 3.0;
        if (f(m1) < f(m2))
            lo = m1;
        else
            hi = m2;
    }
    return (lo + hi) / 2.0;
}

// 三分法（整数版，数组中的单峰）
int ternary_search_int(vector<int>& a) {
    int lo = 0, hi = a.size() - 1;
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (a[m1] < a[m2])
            lo = m1;
        else
            hi = m2;
    }
    // 在 [lo, hi] 中线性查找最大值
    int best = lo;
    for (int i = lo + 1; i <= hi; i++)
        if (a[i] > a[best]) best = i;
    return best;
}

3.5b.8 二分答案 vs 二分查找

对比项	二分查找（Binary Search）	二分答案（Binary on Answer）
作用	在有序数组中找特定值	在答案空间中枚举猜测值
数据结构	需要有序数组	不需要数组，只需 check 函数
check	数组下标的比较	通常是 O(N) 或 O(N log N) 的验证
常见题型	`lower_bound`, `upper_bound`	最大化最小值、最小化最大值
总复杂度	O(log N)	O(log(答案范围) × check 复杂度)

⚠️ 常见错误

错误	原因	修复方案
死循环	`while(lo < hi)` + `lo = mid`，当 `lo+1==hi` 时 `mid = lo` 死循环	改用 `while(lo + 1 < hi)`
答案差 1	`hi` 设置为 `max_val` 而非 `max_val + 1`	`hi = 答案上界 + 1`（左闭右开）
check 溢出	`check` 中累加超过 int 范围	使用 `long long`
浮点精度不足	迭代次数太少	设为 100 次，不必再少
三分法用于非单峰函数	只有单峰函数才能三分	先确认函数的单峰性质

💪 练习题（共 8 道，全部含完整解答）

🟢 基础练习（1~3）

题目 1：切绳子（浮点二分）
N 根绳子，长度已知，要切出 K 根相同长度的绳子，求最大长度（精确到 0.01m）。

示例：

N=4, K=11
绳子长度：8.02 7.43 4.57 5.39
答案：2.00

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<double> a;

bool check(double len) {
    int total = 0;
    for (double x : a) total += (int)(x / len);
    return total >= k;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    for (double& x : a) cin >> x;
    
    double lo = 0, hi = *max_element(a.begin(), a.end());
    for (int iter = 0; iter < 100; iter++) {
        double mid = (lo + hi) / 2.0;
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    
    // 保留两位小数
    printf("%.2f\n", lo);
    return 0;
}

关键： 浮点二分用「循环固定次数（100次）」而非「精度判断」，避免精度问题导致死循环。100 次后误差约 (hi-lo)/2^100，远小于题目要求。

题目 2：数组分组（最大值最小化）
将长度 N 的数组分为恰好 K 组连续子数组，使各组元素之和的最大值最小，输出该最小最大值。

示例：

N=5, K=3, 数组=[1,2,3,4,5]
最优分法：[1,2],[3],[4,5] → 最大组和 = max(3,3,9)=9？
不对，试 [1,2,3],[4],[5] → max(6,4,5)=6 ✓
输出：6

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<long long> a;

bool check(long long maxSum) {
    for (long long x : a) if (x > maxSum) return false;  // 单元素超限
    int groups = 1; long long cur = 0;
    for (long long x : a) {
        if (cur + x > maxSum) { groups++; cur = x; }
        else cur += x;
    }
    return groups <= k;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    long long total = 0;
    for (long long& x : a) { cin >> x; total += x; }
    
    long long lo = *max_element(a.begin(), a.end()) - 1;
    long long hi = total + 1;
    while (lo + 1 < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << "\n";
    return 0;
}

追踪（a=[1,2,3,4,5], k=3）：

lo=4（max元素-1）, hi=16（总和+1）
mid=10 → check: [1..5]=15>10→[1,2,3,4]=10✓,[5] → 2组≤3 ✓ → hi=10
mid= 7 → check: [1,2,3]=6,[4]=4,[5]=5 → 3组≤3 ✓ → hi=7
mid= 5 → check: [1,2]=3,[3]=3,[4]=4→加5=9>5→新组[5] → 4组>3 ✗ → lo=5
mid= 6 → check: [1,2,3]=6,[4]=4,[5]=5 → 3组≤3 ✓ → hi=6

lo+1=6=hi，输出 hi=6 ✓

题目 3：查找有序矩阵第 K 小元素
N×N 的矩阵，每行每列均递增。找第 K 小的元素。

提示： 对答案二分，check(x) = 矩阵中 ≤ x 的元素个数 ≥ K。

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<vector<int>> mat;

// 统计矩阵中 <= x 的元素个数
// 利用行有序性：每行二分
int count_le(int x) {
    int cnt = 0;
    for (auto& row : mat) {
        // upper_bound 返回第一个 > x 的迭代器
        cnt += (int)(upper_bound(row.begin(), row.end(), x) - row.begin());
    }
    return cnt;
}

int main() {
    cin >> n >> k;
    mat.assign(n, vector<int>(n));
    for (auto& row : mat) for (int& x : row) cin >> x;
    
    int lo = mat[0][0] - 1;
    int hi = mat[n-1][n-1];
    
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (count_le(mid) >= k) hi = mid;  // mid 可能是答案，尝试更小
        else lo = mid;
    }
    
    cout << hi << "\n";  // 最小的使 count_le >= k 的值
    return 0;
}

复杂度： O(N log N log(max-min))，N=300, max=10^9 时约 300×8×30 ≈ 72000 次操作，极快。

🟡 进阶练习（4~6）

题目 4：安置奶牛（最大化最小值）
N 个牛栏分布在数轴上（坐标已知），放 C 头奶牛，使任意两头奶牛之间的距离尽可能大。
求最大的「最小相邻距离」。

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> pos;

bool check(int D) {
    int cows = 1, last = pos[0];
    for (int i = 1; i < n; i++) {
        if (pos[i] - last >= D) { cows++; last = pos[i]; }
        if (cows >= c) return true;
    }
    return cows >= c;
}

int main() {
    cin >> n >> c;
    pos.resize(n);
    for (int& x : pos) cin >> x;
    sort(pos.begin(), pos.end());
    
    int lo = 0, hi = pos.back() - pos.front() + 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    cout << lo << "\n";
    return 0;
}

追踪（pos=[1,2,4,8,9], c=3）：

排序后：[1,2,4,8,9]，lo=0，hi=9

mid=4：check(4)：1放1，下一个≥1+4=5→放8，下一个≥8+4=12>9→只放2头 < 3 ✗ → lo=4
mid=6：check(6)：放1，≥7→放8，≥14>9→2头 < 3 ✗ → lo=6（⚠️等等）

重新算：
mid=4：1(place)→2(dist=1<4跳)→4(dist=3<4跳)→8(dist=4✓,place)→9(dist=1<4跳) → 2头 < 3 ✗ → lo=4？

不对，重新算 c=3：
mid=3：1(place)→2(1<3)→4(3✓,place)→8(4✓,place) → 3头 ≥ 3 ✓ → lo=3
mid=4：1(place)→4(3<4)→8(4✓,place)→9(1<4) → 2头 < 3 ✗ → hi=4

lo+1=4=hi，答案 lo=3

题目 5：跳石头（NOIP 2015）
河中有 N 块石头，起点到终点距离 L。可以移除最多 M 块石头，使最短跳跃距离最大。
求这个最大的「最短跳跃距离」。

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int l, n, m;
vector<int> pos;  // 包含起点0和终点l

bool check(int minDist) {
    // 统计需要移除多少块石头，使所有相邻距离 >= minDist
    int removed = 0, prev = 0;
    for (int i = 1; i < (int)pos.size(); i++) {
        if (pos[i] - prev < minDist) removed++;  // 这块石头太近，移除
        else prev = pos[i];
    }
    return removed <= m;
}

int main() {
    cin >> l >> n >> m;
    pos.push_back(0);  // 起点
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        pos.push_back(x);
    }
    pos.push_back(l);  // 终点
    sort(pos.begin(), pos.end());
    
    int lo = 0, hi = l + 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    cout << lo << "\n";
    return 0;
}

关键： check(D) 采用贪心——从左到右扫描，遇到距离 < D 的石头就移除（因为移除它一定不差于移除其他石头）。统计移除数量是否 ≤ M。

题目 6：最优比率（分数规划）
给定 N 个任务，每个任务有完成时间 t[i] 和价值 v[i]。
选恰好 K 个任务，最大化 总价值 / 总时间。输出最大比率（精度 1e-6）。

✅ 完整解答

核心转化（0-1 分数规划）：
二分比率 λ，检查是否存在选 K 个任务使得 Σv[i] / Σt[i] ≥ λ，
等价于 Σ(v[i] - λ*t[i]) ≥ 0。
对 w[i] = v[i] - λ*t[i] 取最大的 K 个，若其和 ≥ 0，则 λ 可行。

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<double> t_arr, v_arr;

bool check(double lam) {
    // 计算每个任务的 "净收益" w[i] = v[i] - lam * t[i]
    vector<double> w(n);
    for (int i = 0; i < n; i++) w[i] = v_arr[i] - lam * t_arr[i];
    
    // 取最大的 k 个净收益之和
    sort(w.begin(), w.end(), greater<double>());
    double sum = 0;
    for (int i = 0; i < k; i++) sum += w[i];
    
    return sum >= 0;  // 能否达到比率 lam？
}

int main() {
    cin >> n >> k;
    t_arr.resize(n); v_arr.resize(n);
    for (int i = 0; i < n; i++) cin >> t_arr[i] >> v_arr[i];
    
    double lo = 0, hi = 1e6;  // 比率的上下界
    for (int iter = 0; iter < 100; iter++) {
        double mid = (lo + hi) / 2.0;
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    
    printf("%.6f\n", lo);
    return 0;
}

为什么这样转化正确？
若最优比率为 λ*，则对任意 λ < λ*，都能选到 K 个任务满足 Σ(v[i]-λt[i]) ≥ 0；
对任意 λ > λ*，不可能满足。这正是「单调性」的体现。

🔴 挑战练习（7~8）

题目 7：最小化最大花费（二分 + 图）
N 个城市，M 条带权无向边。需要选一些边，连通所有城市，使最大边权最小。
（即最小生成树的最大边权最小化。）

✅ 完整解答

二分视角： 二分「允许的最大边权」= W，check(W) = 只用权重 ≤ W 的边，是否能连通所有城市。
等价于：Kruskal 算法跑到权重 W 时，是否已经形成生成树。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) { iota(pa.begin(), pa.end(), 0); }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
};

int n, m;
vector<tuple<int,int,int>> edges;  // {w, u, v}

bool check(int maxW) {
    DSU dsu(n);
    int cnt = 0;
    for (auto& [w, u, v] : edges) {
        if (w > maxW) break;
        if (dsu.unite(u, v)) cnt++;
    }
    return cnt == n - 1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edges.push_back({w, u, v});
    }
    sort(edges.begin(), edges.end());
    
    int lo = 0, hi = get<0>(edges.back()) + 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    
    cout << (check(hi) ? hi : -1) << "\n";  // -1 表示无法连通
    return 0;
}

注：实际上这等价于直接跑 Kruskal 的最大边权，无需二分——但本题作为二分思维的练习，两种做法均正确。

题目 8：最小化等待时间（二分 + 贪心）
N 个顾客到达超市，每人需要服务时间 s[i]，超市有 K 个服务台。
每个服务台每次服务一人，服务完后立即接待下一人。
合理安排顾客顺序，使所有顾客等待时间之和最小。

提示： 先证明「等待时间之和最小」等价于「将服务时间最短的顾客优先」，然后贪心排序直接求答案（无需二分）。
挑战版：若每个顾客有到达时刻限制 a[i]，需要对答案二分「最大等待时间」。

✅ 完整解答（贪心版）

证明： 若服务台同时开始，将顾客按服务时间升序排列，使等待时间之和最小（SPT规则）。

K 个服务台版本（贪心 + 优先队列）：
维护 K 个服务台的当前空闲时刻，每次将下一位顾客分配到最早空闲的服务台。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> s(n);
    for (int& x : s) cin >> x;
    sort(s.begin(), s.end());  // 按服务时间升序（SPT 规则）
    
    // K 个服务台的空闲时刻（最小堆）
    priority_queue<long long, vector<long long>, greater<long long>> free_time;
    for (int i = 0; i < k; i++) free_time.push(0);
    
    long long total_wait = 0;
    for (int i = 0; i < n; i++) {
        long long earliest = free_time.top(); free_time.pop();
        total_wait += earliest;  // 顾客 i 的等待时间 = 服务台空闲时刻
        free_time.push(earliest + s[i]);
    }
    
    cout << total_wait << "\n";
    return 0;
}

示例（n=4, k=2, s=[3,1,4,2]）：

排序后 s = [1,2,3,4]
服务台：[0,0]（初始空闲时刻）

顾客0(s=1)：分配到台0，台0变为0+1=1，wait=0
服务台：[0,1]
顾客1(s=2)：分配到台0（最早空闲），台0变为0+2=2，wait=0
服务台：[1,2]
顾客2(s=3)：分配到台0（空闲时=1），wait=1，台变为1+3=4
服务台：[2,4]
顾客3(s=4)：分配到台0（空闲时=2），wait=2，台变为2+4=6

总等待时间 = 0+0+1+2 = 3

💡 章节联系： 二分答案是竞赛中最实用的思想之一，贯穿 USACO Bronze→Gold 的所有级别。它通常与贪心（check 函数的核心工具）和前缀和（快速验证）结合使用，是「思想轻巧、代码简洁」的典范。

C++ 竞赛编程：USACO 学习指南