10 二分答案

GESP C++ 五级讲义：二分答案精讲

核心目标：理解二分答案的核心思想与适用条件，掌握“最小化最大值”和“最大化最小值”两类问题的解题框架，熟练设计 check 判定函数，能分析二分答案的复杂度。
二分答案就是“猜答案 + 验证”——答案具有单调性时，把“求最优解”转化为“判定是否可行”；框架固定：确定范围 → 二分 mid → check 判定 → 更新边界；check 函数是灵魂，通常用贪心或模拟实现。

一、考纲定位

根据 CCF 官方考纲，五级知识点第（6）条明确要求：“掌握二分查找和二分答案算法（也称二分枚举法）的基本原理，能够在有序数组中快速定位目标值。 ”考核目标进一步要求：“熟悉二分法、分治法、贪心算法和递归算法的算法思想，能够根据实际情况选择合适的算法并完成解决相应的问题”。

二分答案在五级考试中的考查分布：

考点	重要程度	典型考法
二分答案基本原理	★★★★★	选择题、编程题
“最小化最大值”模型		编程题高频
“最大化最小值”模型		编程题高频
check 函数设计		编程题核心难点
二分答案边界确定	★★★★☆	代码填空
二分答案综合应用	★★★★★	编程题

从近几场五级真题来看，二分答案已经成为编程题的“常客”：2025年6月的“奖品兑换”、2025年12月的“数字移动”、2026年3月的“找数”等题目都涉及二分思想的应用。

二、什么是二分答案

2.1 核心思想

二分答案适用于“最小化最大值”或“最大化最小值”类最优化问题。核心特征：直接求解最优值困难，但判断“给定值是否可行”相对容易，且答案具有单调性。

直观理解：就像猜数字游戏——你心里想一个数（最优解），我每次猜一个中间值，你告诉我“大了”或“小了”，我就能不断缩小范围，最终猜到答案。二分答案的本质是：把“求最优解”转化为“判定是否可行”。

2.2 适用条件

二分答案必须同时满足两个条件：

条件	含义	判断方法
答案具有单调性	若 x 可行，则比 x 更“宽松”的值也可行（或反之）	思考“x 可行时，x+1 是否一定可行？”
check 函数可高效实现	给定候选值，能快速判断是否可行	check 通常是 O(n) 的贪心或模拟

单调性的两种形式：

形式一：若 x 可行，则所有 ≥ x 的值都可行 → 找最小可行值。
形式二：若 x 可行，则所有 ≤ x 的值都可行 → 找最大可行值。

2.3 二分答案 vs 二分查找

对比项	二分查找	二分答案
目标	在有序数组中找目标值	在答案区间中找最优值
前提	数组有序	答案具有单调性
判断函数	`a[mid] == target`	`check(mid)` 是否可行
返回值	目标下标或 -1	最优答案
二分对象	数组下标	答案的数值范围

三、二分答案的解题框架

3.1 通用四步框架

第一步：确定二分范围 [lo, hi]
第二步：确定 check 函数（判定 mid 是否可行）
第三步：确定单调性方向（找最小可行还是最大可行）
第四步：套用二分模板，更新边界

3.2 模板一：找最小可行值

若 x 可行，则所有 ≥ x 的值都可行。目标是找最小的可行值。

int lo = 最小可能值, hi = 最大可能值;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) {
        hi = mid;        // mid 可行，尝试更小
    } else {
        lo = mid + 1;    // mid 不可行，必须更大
    }
}
return lo;   // 最小可行值

关键：check(mid) 为真时，hi = mid（不是 hi = mid - 1），因为 mid 本身可能是答案。

3.3 模板二：找最大可行值

若 x 可行，则所有 ≤ x 的值都可行。目标是找最大的可行值。

int lo = 最小可能值, hi = 最大可能值;
while (lo < hi) {
    int mid = lo + (hi - lo + 1) / 2;   // 注意：+1 使 mid 偏右
    if (check(mid)) {
        lo = mid;        // mid 可行，尝试更大
    } else {
        hi = mid - 1;    // mid 不可行，必须更小
    }
}
return lo;   // 最大可行值

关键：mid = lo + (hi - lo + 1) / 2 中的 +1 不能丢，否则当 lo 和 hi 相邻时会死循环。

3.4 两个模板对比

对比项	找最小可行值	找最大可行值
单调性	x 可行 → 更大的都可行	x 可行 → 更小的都可行
check 真时	`hi = mid`	`lo = mid`
check 假时	`lo = mid + 1`	`hi = mid - 1`
mid 计算	`lo + (hi - lo) / 2`	`lo + (hi - lo + 1) / 2`
记忆	找最小，mid 偏左	找最大，mid 偏右

四、check 函数的设计

check 函数是二分答案的灵魂。它接收一个候选值 mid，判断在这个限制下能否完成任务，返回 bool。

4.1 check 函数的常见实现方式

问题类型	check 的实现思路	复杂度
分割数组	贪心：尽可能少地分割，看是否 ≤ k 段	O(n)
最小距离最大化	贪心：能放就放，看能放几个
花费上限	模拟：只处理花费 ≤ mid 的元素
资源分配	数学：计算可行区间是否非空	O(1)

4.2 check 函数的单调性验证

设计完 check 后，必须验证单调性：若 mid 可行，mid+1 是否一定可行？ 如果这个性质成立，二分才正确。

反例：如果 check 函数不满足单调性，二分答案会得到错误结果。

五、GESP 五级二分答案真题精讲

真题1：奖品兑换（2025年6月）

题目描述：班主任发放了若干张课堂优秀券和作业优秀券。同学们可以用 a 张课堂券和 b 张作业券兑换一份奖品，或者用 b 张课堂券和 a 张作业券兑换一份奖品。小 A 有 n 张课堂券和 m 张作业券，求最多能兑换多少份奖品。

解题思路：设兑换总份数为 k，对 k 进行二分。check(k) 判断 k 份奖品是否可行。

关键转化：设用第一种方式兑换了 x 次，第二种方式兑换了 y 次，则 x + y = k。需要满足：

a*x + b*y ≤ n   （课堂券约束）
b*x + a*y ≤ m   （作业券约束）
0 ≤ x ≤ k, 0 ≤ y ≤ k

由 x + y = k，可得 y = k - x，代入约束：

a*x + b*(k-x) ≤ n  →  (a-b)*x ≤ n - b*k
b*x + a*(k-x) ≤ m  →  (b-a)*x ≤ m - a*k

解出 x 的可行区间，判断是否非空即可。

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

int n, m, a, b;

bool check(int k) {
    if ((a + b) * k > n + m) return false;
    int mi = 0, ma = k;
    // 约束1: (a-b)*x <= n - b*k
    // 约束2: (b-a)*x <= m - a*k
    // 需根据 a-b 的正负分类讨论
    // ...（具体计算可行区间）
    return mi <= ma;
}

signed main() {
    cin >> n >> m >> a >> b;
    if (a > b) swap(a, b);

    int l = 0, r = min(n / a, m / a);
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

关键点：对兑换份数 k 进行二分，check 函数计算在总券数限制下 x 的可行区间是否非空。

真题2：数字移动（2025年12月）

题目描述：序列中每个数字恰好出现两次，每次可以移动一个数字到任意位置，花费等于数字本身。求使所有相同数字在序列中相邻所需的最小花费上限。

解题思路：二分答案 x，判断“只移动数值 ≤ x 的数字”能否完成任务。核心转化：数值 > x 的数字不能移动，必须在原始序列中（忽略可移动数字后）已经成对相邻。

int lo = 0, hi = 最大值;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid;
    else lo = mid + 1;
}
cout << lo;

// check(mid)：忽略所有 <= mid 的元素，检查剩余序列是否成对相邻
bool check(int x) {
    int last = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= x) continue;   // 可移动的数字，忽略
        if (last == 0) last = a[i];
        else if (a[i] == last) last = 0;  // 成对，清除
        else return false;         // 不可移动的数字未成对
    }
    return true;
}

关键点：二分答案 + 贪心判定。将“移动花费 ≤ x”转化为“数值 > x 的数字不可移动，检查剩余序列是否成对相邻”。这是一个典型的“最小化最大值”问题。

真题3：分割数组类问题

题目描述：给定一个长度为 n 的正整数数组，将其分成 k 段连续子数组，使得各段和的最大值最小。求这个最小的最大值。

解题思路：典型的“最小化最大值”问题。二分答案“最大段和”，check 函数贪心判断能否在最大段和 ≤ mid 的前提下分成不超过 k 段。

bool check(int maxSum, int a[], int n, int k) {
    int cnt = 1;        // 至少需要一段
    int curSum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > maxSum) return false;   // 单个元素就超限
        if (curSum + a[i] > maxSum) {
            cnt++;          // 需要新开一段
            curSum = a[i];
        } else {
            curSum += a[i];
        }
    }
    return cnt <= k;    // 段数不超过 k 即可行
}

int main() {
    int lo = 最大元素值, hi = 数组总和;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid, a, n, k)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << endl;
    return 0;
}

关键点：

二分范围：lo = 最大元素值（至少要能装下最大元素），hi = 数组总和（一整段）。
check 函数：贪心分段，尽可能让每段和接近但不超过 maxSum。
这是“最小化最大值”的标准模型。

真题4：最小距离最大化

题目描述：在数轴上有 n 个位置，选择其中 k 个位置放置物品，使得任意两个物品之间的最小距离最大。

解题思路：典型的“最大化最小值”问题。二分答案“最小距离”，check 函数贪心判断能否在最小距离 ≥ mid 的前提下放置 k 个物品。

bool check(int minDist, int pos[], int n, int k) {
    int cnt = 1;              // 第一个位置必选
    int lastPos = pos[0];
    for (int i = 1; i < n; i++) {
        if (pos[i] - lastPos >= minDist) {
            cnt++;
            lastPos = pos[i];
        }
    }
    return cnt >= k;
}

int main() {
    sort(pos, pos + n);       // 必须先排序
    int lo = 0, hi = pos[n-1] - pos[0];
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;   // 找最大，mid 偏右
        if (check(mid, pos, n, k)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << endl;
    return 0;
}

关键点：

二分范围：lo = 0，hi = 最大坐标差。
check 函数：贪心放置，能放就放，看能否放够 k 个。
这是“最大化最小值”的标准模型。

六、二分答案的复杂度分析

二分答案的总复杂度 = 二分次数 × check 函数复杂度。

部分	复杂度	说明
二分次数	O(log(hi - lo))	答案范围的对数
check 函数	通常 O(n)	贪心或模拟
总复杂度	O(n log(答案范围))	适合 n ≤ 10⁵

示例：n = 10⁵，答案范围 10⁹，总复杂度 = 10⁵ × log(10⁹) ≈ 10⁵ × 30 = 3×10⁶，完全可行。

七、二分答案的常见模型

模型	问题描述	check 思路	单调性
最小化最大值	分成 k 段，使最大段和最小	贪心分段	x 可行 → 更大可行
最大化最小值	选 k 个，使最小距离最大	贪心放置	x 可行 → 更小可行
花费上限	移动花费 ≤ x，能否完成	模拟/贪心	x 可行 → 更大可行
资源分配	每份资源 ≤ x，能否满足需求	数学计算	视具体问题
时间限制	时间 ≤ x，能否完成任务	模拟	x 可行 → 更大可行

八、易错点汇总

答案不具有单调性：二分答案的前提是单调性，不满足则不能二分。
check 函数写错：check 是核心，判定逻辑错误会导致整个二分答案错误。
二分范围确定错误：lo 和 hi 必须覆盖所有可能的答案，否则会遗漏。
找最小和找最大的模板混用：找最小用 hi = mid，找最大用 lo = mid，不要搞反。
mid 计算未 +1：找最大可行值时，mid = lo + (hi - lo + 1) / 2 的 +1 不能丢，否则死循环。
check 函数复杂度过高：check 必须是 O(n) 或更低，否则总复杂度会超时。
整数溢出：check 函数中的累加可能溢出，用 long long。
边界值未验证：手动验证 lo 和 hi 两个边界是否满足 check。
输出类型错误：答案可能是 long long，注意输出格式。
忘记排序：某些二分答案问题（如“最大化最小值”的位置选择）需要先对输入排序。

九、速查表

需求	写法	关键注意
找最小可行值	`while(lo<hi){ mid=lo+(hi-lo)/2; if(check(mid)) hi=mid; else lo=mid+1; }`	check 真时 `hi=mid`
找最大可行值	`while(lo<hi){ mid=lo+(hi-lo+1)/2; if(check(mid)) lo=mid; else hi=mid-1; }`	mid 偏右，+1 不能丢
二分范围	`lo = 最小可能值, hi = 最大可能值`	覆盖所有答案
check 函数	`bool check(int mid)`	贪心或模拟，O(n)
最小化最大值	二分“最大值”，check 判断能否满足	x 可行 → 更大可行
最大化最小值	二分“最小值”，check 判断能否满足	x 可行 → 更小可行
总复杂度	O(n log(答案范围))	n ≤ 10⁵ 可行
边界验证	手动验证 lo 和 hi	确保 check 单调

十、总结

二分答案是 GESP 五级算法模块的核心内容，也是编程题的高频考点。

二分答案的核心是“猜答案 + 验证”，把“求最优解”转化为“判定是否可行”。
适用条件：答案具有单调性，check 函数可高效实现。
两种模型：最小化最大值（找最小可行值）、最大化最小值（找最大可行值）。
找最小可行值：check(mid) 真时 hi = mid，假时 lo = mid + 1。
找最大可行值：check(mid) 真时 lo = mid，假时 hi = mid - 1，mid 计算要 +1。
check 函数是灵魂，通常用贪心或模拟实现，复杂度 O(n)。
二分范围必须覆盖所有可能的答案，lo 和 hi 不能遗漏。
总复杂度 = O(n log(答案范围))，适合 n ≤ 10⁵ 的数据规模。
典型模型：分割数组、最小距离最大化、花费上限、资源分配。
多练“奖品兑换”“数字移动”“分割数组”“最小距离最大化”四类题。

复习建议：先理解二分答案的核心思想（猜答案 + 验证），再掌握两个模板的边界更新方式；然后重点攻克 check 函数的设计，从“分割数组”和“最小距离最大化”两个经典模型入手；最后练习“奖品兑换”和“数字移动”两道真题，体会 check 函数的实际写法。考试中先判断题目是否满足二分答案的适用条件，再确定二分范围和单调性方向，然后设计 check 函数，最后套用模板并验证边界。