二分答案与check单调判定函数
给你 根长短不一的原木,要求切成至少 段等长的小木头,每段最长能切多少厘米?或者河道中分布着 块岩石,最多允许移走 块,如何让选手每次跳跃的“最短距离尽可能大”?许多同学面对这类复杂的全局最优化问题,第一反应是硬推贪心公式或设计动态规划状态,结果越推越乱、处处反例。其实,只要换一个视角就会豁然开朗——如果从正面“直接算出最优答案”难如登天,但反过来“给你一个猜测的答案 mid,验证它能不能做到”却轻而易举,我们就可以直接在答案的取值范围上折半猜数! 在 GESP 五级认证以及 CSP-J/S 初赛完善程序与复赛核心算法题中,二分答案(Binary Search on Answer)的题眼识别、答案空间单调两段性证明、上下界 [L, R] 的严密界定,以及结合贪心或模拟构造 判定函数 check(mid) 的标准范式,是从基础模拟跨越到高阶算法设计的分水岭。本文将带你彻底打通这套“化求值为判定”的降维打击思维。
🎯 考纲锚点与核心痛点
📍 对应考点:掌握二分答案的核心建模思想,能够敏锐识别“最小值最大化 / 最大值最小化”等具备答案单调性的最优化问题,独立完成答案值域上下界
[L, R]界定、 贪心/模拟判定函数check(mid)构造以及 整体时间复杂度推导。 🎯 适用等级:GESP 五级考点 | CSP-J/S 初赛/复赛必考
在考场实战与初赛阅读/完善程序题中,考生最容易在以下三大痛点上折戟:
- “只会对现成有序数组二分下标,看不出‘虚空中的答案’也能二分”:思维被死死限制在“给你一个升序数组
a[]找元素”,一旦题目给出的原始数组乱序甚至严禁打乱顺序(如按序装箱、划分连续子数组),就完全想不到二分的对象其实是最终所求的那个答案数值 ; - “分不清
check(mid)为真时该往左缩还是往右缩,缩界与中点公式配反导致死循环”:在“最大值最小化”与“最小值最大化”两类相反模型中,搞不清合法区(true)落在左半段还是右半段,把l = mid与r = mid写反,或者写了l = mid却漏掉中点+ 1当场陷入死循环 TLE; - “上下界
[L, R]凭感觉乱填,遭遇除以0崩溃、漏掉0解或超int溢出”:比如切木头时做a[i] / mid却让mid取到0触发除零错误(RE),或者设l = 1漏掉“连长度1都切不出(答案应为0)”的边界,又或者多元素求和上界高达 却用int存l, r, mid导致溢出 WA!
🧠 一、 核心原理深度拆解(有理论)
1. 逆向降维魔法:从“正面算最优值”到“反面猜数做是非题”
为什么“二分答案”能把一道看似无从下手的难题瞬间降维成基础模拟题?请对比以下两种截然不同的思维难度:
- 正面硬解(最优化求值问题):在 种可能的切法或划分方案中,直接用公式算出最优解 —— 需要同时兼顾全局所有元素的比例分配,正面推导极其痛苦;
- 逆向猜数(是非判定问题
check(mid)):假设裁判先向你透露一个候选数值mid,问你:“答案达到mid这个标准,到底行不行?” 此时,未知的所求量摇身一变,成了已知的硬性阈值常数mid!你只需要顺着题意,用最朴素的贪心或模拟从头扫一遍数组(耗时 ),就能干脆利落地回答true(能做到) 或false(做不到)!
只要这个问题的所有候选答案区间 满足**“0/1 二段单调性”**——即以真实最优解 为分界线,一侧所有值全都回答 true,另一侧所有值全都回答 false,绝不出现 真、假、真 的交替震荡——我们就能在答案值域 上直接套用二分,每次砍掉整整一半候选值,以闪电般的折半速度逼出最优解 !
2. 考场八字题眼与两大经典模型的单调分界全景图
在 GESP 五级与 CSP-J/S 赛场上,只要题干中直接或间接出现 “使……的最大值尽可能小(最大值最小化)” 或 “使……的最小值尽可能大(最小值最大化)” 这八字箴言,95% 以上都是二分答案的标准信号!
这两大模型的 true / false 值域分布恰似一对镜像双生子:
====================================================================================
【二分答案两大母题模型:答案值域 [L, R] 上的 0/1 二段单调分布图】
▶ 模型一:最小值最大化(如:切木头求最长单段长度、跳石头求最大最短跳跃距离)
物理直觉:要求的标准 mid 越低越容易达标(真),标准定得太高材料不够(假)!
答案值域: L -----------------------------------------------------> R (数值从小到大)
check(x): [ 真, 真, 真, 真, | 假, 假, 假, 假 ]
1 1 1 1 | 0 0 0 0
▲ 最优解 x*:左半段【最后一个 true】!
缩界动作: check(mid) 为真 ➔ mid 可行,还能往更大冲刺:l = mid(否则 r = mid - 1)
配套中点: 看见 l = mid 必加 1 ➔ mid = l + (r - l + 1) / 2
▶ 模型二:最大值最小化(如:按序装船求最低运载能力、数列分段使最大段和最小)
物理直觉:给的容量上限 mid 越窄越装不下(假),上限放得越宽越轻松装完(真)!
答案值域: L -----------------------------------------------------> R (数值从小到大)
check(x): [ 假, 假, 假, | 真, 真, 真, 真, 真 ]
0 0 0 | 1 1 1 1 1
▲ 最优解 x*:右半段【第一个 true】!
缩界动作: check(mid) 为真 ➔ mid 够用,尝试往更小压缩:r = mid(否则 l = mid + 1)
配套中点: 看见 r = mid 不加 1 ➔ mid = l + (r - l) / 2
====================================================================================我们将两大模型的要素浓缩为一张考场速查对照表:
| 模型类别 | 典型代表母题 | 值域 check 分布 | check(mid) 为真时的缩界 | check(mid) 为假时的缩界 | 唯一配套 mid 公式 |
|---|---|---|---|---|---|
| 最小值最大化 | 原木切割、跳石头、牛棚最大最近间距 | 前 true 后 false(找末个 true) | l = mid(可行,试着调大) | r = mid - 1(超标,必须调小) | l + (r - l + 1) / 2 |
| 最大值最小化 | 数列分段、包裹按序装船、抄书问题 | 前 false 后 true(找首个 true) | r = mid(够用,试着压小) | l = mid + 1(不够,必须放宽) | l + (r - l) / 2 |
3. 三步构造 check(mid) 标准范式与时间复杂度账本
写任何一道二分答案题,只需严格按以下“流水线三步曲”推进:
- 第一步:严密锁死答案上下界
[L, R]:找出答案理论上最小可能取到的值 (如单件最重货物 ,或含无解时的0)与最大可能取到的值 (如所有货物总重 ,或最长那根原木 ),确保真实最优解 ; - 第二步:把
mid当已知常数,贪心/模拟写check(mid):假设答案限制死为mid,用一趟 循环统计“最多能产出多少段”或“最少要消耗多少天/移走多少块石头”,再与题目给定的额度 或 做大小比较返回布尔值; - 第三步:核算整体时间复杂度 :设答案值域跨度为 。无论 有多大,折半次数严格为 (哪怕 仅需约 轮;哪怕 也仅需约 轮!)。每轮调用一次 的
check(mid),总运算量为 。当 时,暴力枚举答案需 次操作必超时,而二分答案仅需 次基本操作,不到 0.02 秒即可跑完!
💡 考场黄金法则(背诵直接套用):
- 【题眼识别与免死记缩界自问法】:见到“最大值最小”或“最小值最大”立刻启动二分答案!考场上根本不用死记左模板还是右模板,只需写下
if (check(mid))后自问一句:“当前mid已经成功了,为了更优,我接下来想试更大的数还是更小的数?”——想试更大就保留右半边写l = mid(必配r = mid - 1与+ 1中点);想试更小就保留左半边写r = mid(必配l = mid + 1与不加1中点)!- 【值域防爆
long long与除零防火墙】:凡是答案上界R或check内部统计量涉及多个元素求和/累加(如 或 ),l、r、mid与累加变量一律无脑开long long;凡是check(mid)内部有除以mid的运算,必须从数学上确保while (l < r)期间mid >= 1恒成立,严防mid == 0触发除零崩溃!
🔍 二、 具象代码与数据推演(有举例)
示例:传送带包裹按序分批装船(“最大值最小化”标准模型)
设传送带上有 件包裹,重量依次为 w[5] = {7, 2, 5, 10, 8}(必须严格按给定顺序装船,不可打乱次序)。要求在最多 天内将全部包裹运完,求货船最低需要多大的单日运载能力?
我们先定上下界:船至少得装得下最重的那一件包裹,故下界 l = max(w) = 10;最多一天把所有包裹全拉走,故上界 r = sum(w) = 32。下面看完整 C++11 推演程序:
#include <iostream>
using namespace std;
int w[5] = {7, 2, 5, 10, 8};
// 贪心判定:当货船单日最大运力定为 cap 时,能否在 2 天内按序运完?
bool check(int cap) {
int days = 1, cur_sum = 0; // 第 1 天起航,当前已装重量为 0
for (int i = 0; i < 5; i++) {
if (cur_sum + w[i] <= cap) {
cur_sum += w[i]; // 当天剩余运力够装,贪心塞进同一天
} else {
days++; // 当天装不下了,新开一天装当前包裹
cur_sum = w[i];
}
}
return days <= 2; // 所需总天数不超过 2 天即为可行
}
int main() {
int l = 10, r = 32; // 答案闭区间 [max_w, sum_w] = [10, 32]
while (l < r) {
int mid = l + (r - l) / 2; // 搭配 r = mid,向下取整不加 1
if (check(mid)) {
r = mid; // 运力 mid 够用,尝试往更小压缩
} else {
l = mid + 1; // 运力 mid 不足,必须提高至 mid + 1
}
}
cout << "Min capacity: " << l << endl;
return 0;
}分步二分猜数与 check(mid) 贪心装船推演表
| 迭代轮次 | 当前答案区间 [l, r] | 猜测运力 mid | check(mid) 按序贪心装船切分过程 | 所需天数与判定结果 | 缩界动作 | 缩界后新区间 |
|---|---|---|---|---|---|---|
| 第 1 轮 | [10, 32] | 10 + 22/2 = 21 | 第1天 {7,2,5}=14;第2天 {10,8}=18 | 2 <= 2(真) | r = mid = 21 | [10, 21] |
| 第 2 轮 | [10, 21] | 10 + 11/2 = 15 | 第1天 {7,2,5}=14;第2天 {10}=10;第3天 {8}=8 | 3 <= 2(假) | l = mid + 1 = 16 | [16, 21] |
| 第 3 轮 | [16, 21] | 16 + 5/2 = 18 | 第1天 {7,2,5}=14;第2天 {10,8}=18 | 2 <= 2(真) | r = mid = 18 | [16, 18] |
| 第 4 轮 | [16, 18] | 16 + 2/2 = 17 | 第1天 {7,2,5}=14;第2天 {10}=10;第3天 {8}=8 | 3 <= 2(假) | l = mid + 1 = 18 | [18, 18](退出) |
程序标准输出:
Min capacity: 18请仔细观察推演过程:原始包裹数组 {7, 2, 5, 10, 8} 完全是乱序的,且一行排序代码都没写!但答案区间 [10, 32] 上的判定结果却是极其规整的 [10..17 全假 | 18..32 全真]。仅仅调用了 4 次简单的贪心加法,二分就把唯一分界点 18 死死锁定!
⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级真题与 CSP-J 考场上,以下三个隐蔽陷阱是导致二分答案莫名 WA 或 RE 的头号元凶:
❌ 易错点 1:混淆“数据有序”与“答案单调”,手贱对不能改序的原数组调 sort!
- 错误操作:一看到要用二分,肌肉记忆发作,上来先写一句
sort(w, w + n);,然后再开始二分答案。 - 为什么错:二分答案要求具备单调性的是“关于答案 的布尔函数
check(x)”,绝不是题目输入的原始数组! 在上文的传送带装船、数列连续分段、河道岩石坐标等模型中,元素的先后顺序是题目的刚性物理约束(例如把{7, 2, 5, 10, 8}排成{2, 5, 7, 8, 10}后,第 1 天{2, 5, 7}=14、第 2 天{8, 10}=18碰巧还是 18,但若换成{10, 2, 10}分 2 天,原序最小运力为12,排序成{2, 10, 10}后最小运力就变成了20,全盘算错!)。 - 正确规范:动手写
sort前先审清题意——只有题目明确允许任意重排元素(如给牛棚选位置放牛,牛棚坐标乱序给出),才需要先对坐标数组排序;凡是涉及“连续子段”、“先后到达”的问题,严禁打乱原数组!
❌ 易错点 2:下界 L 设得过小,引发除以 0 崩溃(RE)或超重元素“假装船” Bug!
- 两类致命现场:
- 除零崩溃(Floating point exception):在切木头问题中,
check(mid)里写了cnt += a[i] / mid;。如果误把模板写成向下取整且l = 0, r = 1,算出mid = 0执行除以0,程序当场崩溃 RE! - 超重元素穿透:在包裹装船
check(cap)中,如果偷懒把左边界写成l = 0(而非max_w = 10),当测试cap = 8时,遇到重量为10的包裹,代码走else { days++; cur_sum = w[i]; }竟然把重达10的包裹硬塞进了最大承重只有8的船里,算出错误的true!
- 除零崩溃(Floating point exception):在切木头问题中,
- 正确规范:
- 装船/数列分段模型的左边界必须严格取
l = max(w[i])(或者在check(cap)循环第一句加上防御守卫if (w[i] > cap) return false;); - 切木头模型求最大值(可能答案为
0)时,设l = 0, r = max_len并严格配向上取整mid = l + (r - l + 1) / 2——只要还在while (l < r)循环内,必有 ,故mid >= 1永远成立,既天然覆盖了0解,又从数学上 100% 杜绝了除以0!
- 装船/数列分段模型的左边界必须严格取
❌ 易错点 3:check(mid) 内部累加器或上界 R 用 int 存储,在大测试点溢出变负数!
- 错误写法:有 根木头,每根长 ,写
int cnt = 0; for (...) cnt += a[i] / mid;。 - 为什么错:当二分试探到较小的
mid = 1时,真实切出的总段数为 ,远超 32 位int上限(约 )!cnt发生有符号整数溢出回绕成负数,导致cnt >= k误判为false,原本可行的长度被当成不可行砍掉,痛失大测试点全部分数! - 正确规范:
check内部的计数/求和变量一律声明为long long,且一旦在循环中途发现cnt >= k已提前达标,立即return true;短路退出,既提速又防爆!
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(GESP 五级 / CSP-J 初赛完善程序经典题:跳石头 check 贪心与缩界推演)
题目:河道起点在坐标 0,终点岸在坐标 25,河中间依次排列着 块岩石,坐标存储在数组 int d[5] = {0, 2, 11, 14, 25}; 中(其中 d[0] = 0 为起点,d[4] = 25 为终点)。现允许从河中间的 块岩石里最多移走 块,使得选手从起点一块接一块跳到终点的过程中,最短那一次跳跃距离尽可能大。实现该二分答案的核心代码如下:
bool check(int mid) {
int removed = 0, last_pos = 0;
for (int i = 1; i <= 4; i++) {
if (d[i] - last_pos < mid) {
removed++; // 间距不足 mid,移走岩石
} else {
last_pos = d[i]; // 间距达标,落脚到当前位置
}
}
return removed <= 2;
}
int solve() {
int l = 1, r = 25;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (check(mid)) {
________; // 【空白处】
} else {
r = mid - 1;
}
}
return l;
}请问代码中 ________ 空白处应填入的语句,以及 solve() 最终返回的答案分别是( )
- A.
r = mid,返回值为9 - B.
l = mid,返回值为11 - C.
l = mid,返回值为12 - D.
l = mid + 1,返回值为11
🔍 答案与逐项排除解析:
- 正确答案:B
- 解析过程:
- 锁定缩界语句:题目要求“最短跳跃距离尽可能大”(最小值最大化),且代码中已给出
mid = l + (r - l + 1) / 2(向上取整)与else分支r = mid - 1。当check(mid)返回true时,说明最短跳mid米完全能做到,应当保留mid并尝试向更大的距离冲刺,故空白处必须填l = mid(直接排除 A、D)! - 手工推演
mid = 11与mid = 12的真伪:- 测试
mid = 11:i = 1(2 - 0 = 2 < 11,移走坐标2的岩石,removed = 1);i = 2(11 - 0 = 11 >= 11,落脚last_pos = 11);i = 3(14 - 11 = 3 < 11,移走坐标14的岩石,removed = 2);i = 4(25 - 11 = 14 >= 11,成功跳上终点25)。共移走2 <= 2块岩石,check(11) == true! - 测试
mid = 12:i = 1(2 < 12,removed = 1);i = 2(11 < 12,removed = 2);i = 3(14 - 0 = 14 >= 12,落脚last_pos = 14);i = 4(终点25 - 14 = 11 < 12,还需移走前一块岩石,removed = 3 > 2),check(12) == false! - 因此最大可行答案为
11(排除 C,锁定 B)!
- 测试
- 锁定缩界语句:题目要求“最短跳跃距离尽可能大”(最小值最大化),且代码中已给出
【例题 2 · 判断题】(GESP 五级考纲概念辨析:最值问题与答案单调性前提)
题目:对于任意一个求解整数最优值(最大值或最小值)的算法问题,只要答案具有明确的有穷上下界 ,且我们能够编写出一个时间复杂度为 、能100%准确判断任意给定整数 是否为合法解的函数 bool check(int x),就一定可以在 上通过二分答案算法在 时间内求出全局最优解。( )
🔍 答案与反例证明:
- 结论:错误(×)
- 辨析证明:
- 能写出准确的判定函数
check(x)只是使用二分答案的必要不充分条件;二分答案得以成立的核心命脉是check(x)在 上必须具备严格的“0/1 二段单调性”(即一侧全为true,另一侧全为false)! - 直观反例:假设袋子里有无限枚面值为
3元的硬币,另有总面值不超过10元的若干限制,问在区间 内最多能恰好凑出多少元整钱?我们可以轻松写出判断“能否恰好凑出 元”的函数check(x),但它在 上的返回序列为:x = 1(假), 2(假), 3(真), 4(假), 5(假), 6(真), 7(假), 8(假), 9(真), 10(假)。 - 如果在
[1, 10]上强行二分,首轮取mid = 6(或5):若测到x = 5为false,二分误以为“5 都凑不出,比 5 大的肯定更凑不出”,一刀把右半区间[6, 10]全部砍掉,直接把真正的最大合法解9当垃圾扔掉了!因此,没有二段单调性的最值问题绝不能用二分答案。
- 能写出准确的判定函数
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛必刷母题:原木切割问题)
题目描述:木材厂有 ()根原木,第 根原木的长度为正整数 ()。现在需要将这些原木切割成至少 ()段长度完全相等的小段木头,每小段木头的长度必须为正整数厘米(原木允许有剩余边角料丢弃,但不可将两段碎木头拼接)。请求出每小段木头所能达到的最大长度;如果连长度为 厘米的小段都切不出 段,请输出 0。
输入格式: 第一行包含两个正整数 和 ,分别表示原木根数与所需切割出的最少小段数。 第二行包含 个正整数 ,表示每根原木的初始长度。
输出格式:
输出一行一个非负整数,表示每小段木头的最大可行长度(无法切出则输出 0)。
💡 算法建模与满分避坑要点:
- 单调性识别:小段长度
mid越短,切出的总段数 越多(越容易 ,为true);长度越长切出的段数越少(最终 ,为false)。属于标准的**“最小值最大化(前真后假,找最后一个true)”**模型; - 零解与除零一石二鸟设计:将闭区间直接设为
l = 0, r = max_len,配套向上取整mid = l + (r - l + 1) / 2。只要满足循环条件l < r,必有r - l + 1 >= 2,从而mid >= 1永远成立,绝不可能除以0!若连mid = 1都切不够 段,r会执行1 - 1 = 0与l = 0会合退出,自然输出0,无需任何冗余特判!
#include <iostream>
using namespace std;
const int MAXN = 100005;
long long a[MAXN];
int n;
long long k;
// 贪心判定:当每小段长度定为 len 时,能否切出至少 k 段?
bool check(long long len) {
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += a[i] / len;
if (cnt >= k) {
return true; // 提前达标直接返回,兼顾加速与防累加溢出
}
}
return cnt >= k;
}
int main() {
cin >> n >> k;
long long max_len = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > max_len) {
max_len = a[i];
}
}
// 闭区间 [0, max_len]:兼容 0 解,且 l < r 时 mid >= 1 恒成立绝不除零
long long l = 0, r = max_len;
while (l < r) {
long long mid = l + (r - l + 1) / 2;
if (check(mid)) {
l = mid; // 长度 mid 可行,尝试往更大长度冲刺
} else {
r = mid - 1; // 长度 mid 切不够 k 段,必须缩短
}
}
cout << l << endl;
return 0;
}- 输入样例:
3 7 232 124 456 - 输出样例:(样例解释:当每段长度取
114114时,三根原木分别可切出232 / 114 = 2段、124 / 114 = 1段、456 / 114 = 4段,合计2 + 1 + 4 = 7 >= 7段刚好达标;若长度增至115,第三根原木只能切出456 / 115 = 3段,总段数骤降至2 + 1 + 3 = 6 < 7段不足,故最大可行长度为114。)
本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。
GESP/CSP认证交流QQ群: 688906745
