二分答案与check单调判定函数

二分答案与check单调判定函数

给你 nn 根长短不一的原木,要求切成至少 kk 段等长的小木头,每段最长能切多少厘米?或者河道中分布着 nn 块岩石,最多允许移走 mm 块,如何让选手每次跳跃的“最短距离尽可能大”?许多同学面对这类复杂的全局最优化问题,第一反应是硬推贪心公式或设计动态规划状态,结果越推越乱、处处反例。其实,只要换一个视角就会豁然开朗——如果从正面“直接算出最优答案”难如登天,但反过来“给你一个猜测的答案 mid,验证它能不能做到”却轻而易举,我们就可以直接在答案的取值范围上折半猜数! 在 GESP 五级认证以及 CSP-J/S 初赛完善程序与复赛核心算法题中,二分答案(Binary Search on Answer)的题眼识别、答案空间单调两段性证明、上下界 [L, R] 的严密界定,以及结合贪心或模拟构造 O(n)O(n) 判定函数 check(mid) 的标准范式,是从基础模拟跨越到高阶算法设计的分水岭。本文将带你彻底打通这套“化求值为判定”的降维打击思维。

🎯 考纲锚点与核心痛点

📍 对应考点:掌握二分答案的核心建模思想,能够敏锐识别“最小值最大化 / 最大值最小化”等具备答案单调性的最优化问题,独立完成答案值域上下界 [L, R] 界定、O(n)O(n) 贪心/模拟判定函数 check(mid) 构造以及 O(nlog⁡V)O(n \log V) 整体时间复杂度推导。 🎯 适用等级:GESP 五级考点 | CSP-J/S 初赛/复赛必考

在考场实战与初赛阅读/完善程序题中,考生最容易在以下三大痛点上折戟:

  1. “只会对现成有序数组二分下标,看不出‘虚空中的答案’也能二分”:思维被死死限制在“给你一个升序数组 a[] 找元素”,一旦题目给出的原始数组乱序甚至严禁打乱顺序(如按序装箱、划分连续子数组),就完全想不到二分的对象其实是最终所求的那个答案数值 xx;
  2. “分不清 check(mid) 为真时该往左缩还是往右缩,缩界与中点公式配反导致死循环”:在“最大值最小化”与“最小值最大化”两类相反模型中,搞不清合法区(true)落在左半段还是右半段,把 l = mid 与 r = mid 写反,或者写了 l = mid 却漏掉中点 + 1 当场陷入死循环 TLE;
  3. “上下界 [L, R] 凭感觉乱填,遭遇除以 0 崩溃、漏掉 0 解或超 int 溢出”:比如切木头时做 a[i] / mid 却让 mid 取到 0 触发除零错误(RE),或者设 l = 1 漏掉“连长度 1 都切不出(答案应为 0)”的边界,又或者多元素求和上界高达 101410^{14} 却用 int 存 l, r, mid 导致溢出 WA!

🧠 一、 核心原理深度拆解(有理论)

1. 逆向降维魔法:从“正面算最优值”到“反面猜数做是非题”

为什么“二分答案”能把一道看似无从下手的难题瞬间降维成基础模拟题?请对比以下两种截然不同的思维难度:

  • 正面硬解(最优化求值问题):在 10910^9 种可能的切法或划分方案中,直接用公式算出最优解 x∗x^* —— 需要同时兼顾全局所有元素的比例分配,正面推导极其痛苦;
  • 逆向猜数(是非判定问题 check(mid)):假设裁判先向你透露一个候选数值 mid,问你:“答案达到 mid 这个标准,到底行不行?” 此时,未知的所求量摇身一变,成了已知的硬性阈值常数 mid!你只需要顺着题意,用最朴素的贪心或模拟从头扫一遍数组(耗时 O(n)O(n)),就能干脆利落地回答 true(能做到) 或 false(做不到)!

只要这个问题的所有候选答案区间 [L,R][L, R] 满足**“0/1 二段单调性”**——即以真实最优解 x∗x^* 为分界线,一侧所有值全都回答 true,另一侧所有值全都回答 false,绝不出现 真、假、真 的交替震荡——我们就能在答案值域 [L,R][L, R] 上直接套用二分,每次砍掉整整一半候选值,以闪电般的折半速度逼出最优解 x∗x^*!


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) 标准范式与时间复杂度账本

写任何一道二分答案题,只需严格按以下“流水线三步曲”推进:

  1. 第一步:严密锁死答案上下界 [L, R]:找出答案理论上最小可能取到的值 LL(如单件最重货物 max⁡wi\max w_i,或含无解时的 0)与最大可能取到的值 RR(如所有货物总重 ∑wi\sum w_i,或最长那根原木 max⁡Li\max L_i),确保真实最优解 x∗∈[L,R]x^* \in [L, R];
  2. 第二步:把 mid 当已知常数,贪心/模拟写 check(mid):假设答案限制死为 mid,用一趟 O(n)O(n) 循环统计“最多能产出多少段”或“最少要消耗多少天/移走多少块石头”,再与题目给定的额度 kk 或 mm 做大小比较返回布尔值;
  3. 第三步:核算整体时间复杂度 O(nlog⁡V)O(n \log V):设答案值域跨度为 V=R−LV = R - L。无论 VV 有多大,折半次数严格为 ⌈log⁡2V⌉\lceil \log_2 V \rceil(哪怕 V=109V = 10^9 仅需约 3030 轮;哪怕 V=1018V = 10^{18} 也仅需约 6060 轮!)。每轮调用一次 O(n)O(n) 的 check(mid),总运算量为 O(nlog⁡V)O(n \log V)。当 n=105,V=109n = 10^5, V = 10^9 时,暴力枚举答案需 101410^{14} 次操作必超时,而二分答案仅需 105×30=3×10610^5 \times 30 = 3 \times 10^6 次基本操作,不到 0.02 秒即可跑完!

💡 考场黄金法则(背诵直接套用):

  1. 【题眼识别与免死记缩界自问法】:见到“最大值最小”或“最小值最大”立刻启动二分答案!考场上根本不用死记左模板还是右模板,只需写下 if (check(mid)) 后自问一句:“当前 mid 已经成功了,为了更优,我接下来想试更大的数还是更小的数?”——想试更大就保留右半边写 l = mid(必配 r = mid - 1 与 + 1 中点);想试更小就保留左半边写 r = mid(必配 l = mid + 1 与不加 1 中点)!
  2. 【值域防爆 long long 与除零防火墙】:凡是答案上界 R 或 check 内部统计量涉及多个元素求和/累加(如 ∑ai\sum a_i 或 ∑(ai/mid)\sum (a_i / \text{mid})),l、r、mid 与累加变量一律无脑开 long long;凡是 check(mid) 内部有除以 mid 的运算,必须从数学上确保 while (l < r) 期间 mid >= 1 恒成立,严防 mid == 0 触发除零崩溃!

🔍 二、 具象代码与数据推演(有举例)

示例:传送带包裹按序分批装船(“最大值最小化”标准模型)

设传送带上有 n=5n = 5 件包裹,重量依次为 w[5] = {7, 2, 5, 10, 8}(必须严格按给定顺序装船,不可打乱次序)。要求在最多 m=2m = 2 天内将全部包裹运完,求货船最低需要多大的单日运载能力?

我们先定上下界:船至少得装得下最重的那一件包裹,故下界 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]猜测运力 midcheck(mid) 按序贪心装船切分过程所需天数与判定结果缩界动作缩界后新区间
第 1 轮[10, 32]10 + 22/2 = 21第1天 {7,2,5}=14;第2天 {10,8}=182 <= 2(真)r = mid = 21[10, 21]
第 2 轮[10, 21]10 + 11/2 = 15第1天 {7,2,5}=14;第2天 {10}=10;第3天 {8}=83 <= 2(假)l = mid + 1 = 16[16, 21]
第 3 轮[16, 21]16 + 5/2 = 18第1天 {7,2,5}=14;第2天 {10,8}=182 <= 2(真)r = mid = 18[16, 18]
第 4 轮[16, 18]16 + 2/2 = 17第1天 {7,2,5}=14;第2天 {10}=10;第3天 {8}=83 <= 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);,然后再开始二分答案。
  • 为什么错:二分答案要求具备单调性的是“关于答案 xx 的布尔函数 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!

  • 两类致命现场:
    1. 除零崩溃(Floating point exception):在切木头问题中,check(mid) 里写了 cnt += a[i] / mid;。如果误把模板写成向下取整且 l = 0, r = 1,算出 mid = 0 执行除以 0,程序当场崩溃 RE!
    2. 超重元素穿透:在包裹装船 check(cap) 中,如果偷懒把左边界写成 l = 0(而非 max_w = 10),当测试 cap = 8 时,遇到重量为 10 的包裹,代码走 else { days++; cur_sum = w[i]; } 竟然把重达 10 的包裹硬塞进了最大承重只有 8 的船里,算出错误的 true!
  • 正确规范:
    • 装船/数列分段模型的左边界必须严格取 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) 循环内,必有 r−l+1≥2r - l + 1 \ge 2,故 mid >= 1 永远成立,既天然覆盖了 0 解,又从数学上 100% 杜绝了除以 0!

❌ 易错点 3:check(mid) 内部累加器或上界 R 用 int 存储,在大测试点溢出变负数!

  • 错误写法:有 n=105n = 10^5 根木头,每根长 10810^8,写 int cnt = 0; for (...) cnt += a[i] / mid;。
  • 为什么错:当二分试探到较小的 mid = 1 时,真实切出的总段数为 105×108=101310^5 \times 10^8 = 10^{13},远超 32 位 int 上限(约 2.14×1092.14 \times 10^9)!cnt 发生有符号整数溢出回绕成负数,导致 cnt >= k 误判为 false,原本可行的长度被当成不可行砍掉,痛失大测试点全部分数!
  • 正确规范:check 内部的计数/求和变量一律声明为 long long,且一旦在循环中途发现 cnt >= k 已提前达标,立即 return true; 短路退出,既提速又防爆!

📝 四、 真题实战演练与精析(有例题:3 道)

【例题 1 · 单选题】(GESP 五级 / CSP-J 初赛完善程序经典题:跳石头 check 贪心与缩界推演)

题目:河道起点在坐标 0,终点岸在坐标 25,河中间依次排列着 n=3n = 3 块岩石,坐标存储在数组 int d[5] = {0, 2, 11, 14, 25}; 中(其中 d[0] = 0 为起点,d[4] = 25 为终点)。现允许从河中间的 33 块岩石里最多移走 m=2m = 2 块,使得选手从起点一块接一块跳到终点的过程中,最短那一次跳跃距离尽可能大。实现该二分答案的核心代码如下:

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
  • 解析过程:
    1. 锁定缩界语句:题目要求“最短跳跃距离尽可能大”(最小值最大化),且代码中已给出 mid = l + (r - l + 1) / 2(向上取整)与 else 分支 r = mid - 1。当 check(mid) 返回 true 时,说明最短跳 mid 米完全能做到,应当保留 mid 并尝试向更大的距离冲刺,故空白处必须填 l = mid(直接排除 A、D)!
    2. 手工推演 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 五级考纲概念辨析:最值问题与答案单调性前提)

题目:对于任意一个求解整数最优值(最大值或最小值)的算法问题,只要答案具有明确的有穷上下界 [L,R][L, R],且我们能够编写出一个时间复杂度为 O(n)O(n)、能100%准确判断任意给定整数 xx 是否为合法解的函数 bool check(int x),就一定可以在 [L,R][L, R] 上通过二分答案算法在 O(nlog⁡(R−L))O(n \log(R - L)) 时间内求出全局最优解。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 能写出准确的判定函数 check(x) 只是使用二分答案的必要不充分条件;二分答案得以成立的核心命脉是 check(x) 在 [L,R][L, R] 上必须具备严格的“0/1 二段单调性”(即一侧全为 true,另一侧全为 false)!
    2. 直观反例:假设袋子里有无限枚面值为 3 元的硬币,另有总面值不超过 10 元的若干限制,问在区间 [1,10][1, 10] 内最多能恰好凑出多少元整钱?我们可以轻松写出判断“能否恰好凑出 xx 元”的函数 check(x),但它在 [1,10][1, 10] 上的返回序列为: x = 1(假), 2(假), 3(真), 4(假), 5(假), 6(真), 7(假), 8(假), 9(真), 10(假)。
    3. 如果在 [1, 10] 上强行二分,首轮取 mid = 6(或 5):若测到 x = 5 为 false,二分误以为“5 都凑不出,比 5 大的肯定更凑不出”,一刀把右半区间 [6, 10] 全部砍掉,直接把真正的最大合法解 9 当垃圾扔掉了!因此,没有二段单调性的最值问题绝不能用二分答案。

【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛必刷母题:原木切割问题)

题目描述:木材厂有 nn(1≤n≤1051 \le n \le 10^5)根原木,第 ii 根原木的长度为正整数 aia_i(1≤ai≤1081 \le a_i \le 10^8)。现在需要将这些原木切割成至少 kk(1≤k≤1081 \le k \le 10^8)段长度完全相等的小段木头,每小段木头的长度必须为正整数厘米(原木允许有剩余边角料丢弃,但不可将两段碎木头拼接)。请求出每小段木头所能达到的最大长度;如果连长度为 11 厘米的小段都切不出 kk 段,请输出 0。

输入格式: 第一行包含两个正整数 nn 和 kk,分别表示原木根数与所需切割出的最少小段数。 第二行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n,表示每根原木的初始长度。

输出格式: 输出一行一个非负整数,表示每小段木头的最大可行长度(无法切出则输出 0)。

💡 算法建模与满分避坑要点:

  1. 单调性识别:小段长度 mid 越短,切出的总段数 ∑⌊ai/mid⌋\sum \lfloor a_i / \text{mid} \rfloor 越多(越容易 ≥k\ge k,为 true);长度越长切出的段数越少(最终 <k< k,为 false)。属于标准的**“最小值最大化(前真后假,找最后一个 true)”**模型;
  2. 零解与除零一石二鸟设计:将闭区间直接设为 l = 0, r = max_len,配套向上取整 mid = l + (r - l + 1) / 2。只要满足循环条件 l < r,必有 r - l + 1 >= 2,从而 mid >= 1 永远成立,绝不可能除以 0!若连 mid = 1 都切不够 kk 段,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
  • 输出样例:
    114
    (样例解释:当每段长度取 114 时,三根原木分别可切出 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

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于