椰程信奥·互动课件 专题8·二分（二）·二分答案
10:00 1 / 14
🧭 椰程信奥 · CSP复赛专题系列

专题8 · 二分（二）· 二分答案

上一讲二分的是「数组里的下标」，这一讲二分的是「答案本身」。
当题目问「最大能是多少 / 最小能是多少」时，直接求很难，但验证一个值行不行往往很简单——
这正是二分答案的用武之地。

伐木工人砍树 数列分段 Section II 最大值最小化 / check 函数
本质

把「求最优」变成「判定可行」

二分查找找的是「下标」，二分答案找的是「值」——判据不同二分查找（专题7）判据：a[mid] 与 目标值 谁大有序数组二分答案（本讲）不可行可行判据：check(mid) 能不能做到答案的值域共同点：都要「一半一半地砍」；差别：本讲砍的是答案的值域，不是数组下标。

🔍 上一讲：二分查找

在一个已有的有序数组里找位置。
候选集合是显式的（下标 1…n）。

🎯 这一讲：二分答案

在答案的可能取值里找最优的那个。
候选集合是隐式的（一个数值区间）。

核心转换：直接求「最大 H」很难，但给你一个 H，判断它能不能达标通常只要扫一遍数组。既然「判定」容易、「求最优」难，那就二分着去判定。
题干出现「最大能是多少」「最小能是多少」「至少 / 至多」，而且暴力枚举答案会超时 —— 十有八九是二分答案。
3D🎲 二分答案 = 把求最优转成判可行🖱 拖拽旋转 · 双击复位
为什么用 3D：二分答案抽象在「答案不是一个位置，是一个高度」。用一片可升降的锯片平面穿过立体树柱，单调性一眼可见。
方法

写之前先想清楚这三件事

能不能二分答案，看这三件事——缺一件就不能用要素 1 · 单调性越小越容易做到越大越难做到中间必有一个分界要素 2 · check 函数给一个值判断能不能做到通常 O(n) 贪心要素 3 · 边界左界一定可行右界一定不可行别从 0 开始瞎猜考场最常见的错误：边界取错（左界应为 max(a) 之类的下界）与 check 里没开 long long。

① 答案范围 [l, r]

最小可能值与最大可能值。
技巧：下界常取「单元素极值」，上界常取「总和」。

② 单调性

答案越大 → 越容易（或越难）满足？
必须同向变化，否则不能二分。
例：H 越大，木料越少（越难达标）。

③ check(x) 函数

给定候选答案 x，判定是否可行。
一般是 O(n) 的扫描或贪心。

复杂度：二分 O(log 范围) 次 × check 的 O(n) = O(n log V)。V 是答案范围大小，通常 10⁹ 也只要 30 次。
最大的坑：单调性方向。先问自己「答案变大时，是更容易满足还是更难？」——想反了，二分的收缩方向就全反了。写之前先用两个具体的 x 手动验一遍。
识别

最大值最小化 / 最小值最大化

📉 最大值最小化

问法：「分成 m 段，让最大的那段尽量小」。

二分方向：候选 X 越大 → 需要的段数越少 → 越容易满足。
所以 check(X) = 段数 ≤ m，求最小满足值（模板①）。

📈 最小值最大化

问法：「锯片尽量高，同时保证木料够」。

二分方向：高度 H 越大 → 木料越少 → 越难满足。
所以 check(H) = 木料 ≥ m，求最大满足值（模板②）。

注意：「问法」和「模板」不是一一对应的。要看的是 check 成立时该往哪边收缩，而不是题目里写的是"最大"还是"最小"。
记住上一讲的判据：是 l = mid 还是 r = mid，决定 mid 要不要 +1。
互动

砍树 · 二分答案模拟器

树高 [4, 42, 40, 26, 46]，需要 20 米木料。点击「下一步」开始二分高度 H。
例题 1

伐木工人砍树：最典型的二分答案

需要 m 米木料，锯片高度 H 越高、砍到的木料越少。问 H 最高能设多少。

① 范围

H ∈ [0, 最大树高]。样例中最大树高 46。

② 单调性

H ↑ → 木料 ↓。
单调递减的可达性。

③ check(H)

累加 max(0, aᵢ − H)，判断 ≥ m。

样例推演：H=36 时，木料 = (42−36)+(40−36)+(46−36) = 6+4+10 = 20 ≥ 20 ✓。H=37 时 = 5+3+9 = 17 < 20 ✗。所以答案就是 36。
有人想「从最大树高往下试，试到不够就停」。那要试 O(maxH) 次，最大树高 10⁹ 时直接超时。二分只要 30 次。
例题 1

砍树 · 代码走读

typedef long long ll;
ll mx = 0;                              // 最大树高，作为上界
for(i=0;i<n;i++){ cin>>a[i]; if(a[i]>mx) mx=a[i]; }
ll l=0, r=mx, ans=0;
while(l <= r){
  ll mid = (l+r)/2;
  ll wood = 0;
  for(i=0;i<n;i++) if(a[i] > mid) wood += a[i] - mid;
  if(wood >= m){ ans = mid; l = mid+1; }   // 够→还能更高
  else          { r = mid-1; }            // 不够→必须降低
}
cout << ans << "\n";
三个坑：① 必须用 long long——n=10⁶、树高 10⁹ 时木料可达 10¹⁵，int 直接溢出；② 上界取 最大树高而不是总和，否则多做十几次无效二分；③ check 里 if(a[i] > mid) 不能省，否则低于 H 的树会贡献负数木料。
例题 2

数列分段：最大值最小化

把 n 个数分成 m 段，让「最大的那段的和」尽量小。

① 范围

下界 = 最大元素（一段至少装下它）；
上界 = 总和（全放一段）。

② 单调性

X ↑ → 每段能装更多 → 需要段数 ↓。
X 太大时只需 1 段，太小时要 n 段。

③ check(X)

贪心：从左往右装，装不下就新开一段。
统计段数，判断 ≤ m。

样例：[4,2,4,5,1]，m=3。X=6 时贪心分段 → [4,2][4][5,1]，3 段 ≤ 3 ✓。X=5 时 → [4][2][4][5,1]，4 段 > 3 ✗。所以答案是 6。
为什么 check 可以贪心？要让段数最少，每段就应该尽可能装到上限——能装就装。这个贪心是正确的，不必怀疑。统计出来的段数是「在 X 限制下最少需要几段」。
例题 2

数列分段 · 代码走读

ll l = 0, r = 0;
for(i=1;i<=n;i++){ cin>>a[i]; if(a[i]>l) l=a[i]; r+=a[i]; }
// l = 单元素最大值（下界）   r = 总和（上界）
while(l < r){
  ll mid = (l+r)/2;
  int cnt = 1; ll cur = 0;              // ★ cnt 从 1 开始
  for(i=1;i<=n;i++){
    if(cur + a[i] <= mid) cur += a[i];
    else { cnt++; cur = a[i]; }
  }
  if(cnt <= m) r = mid;                 // 段数够少→上限还能更小
  else         l = mid+1;
}
cout << l << "\n";
三个坑：① cnt 初值是 1 不是 0（至少有一段），写成 0 会让段数少算一段；② 下界必须取最大元素，取 0 会让 mid 过小、贪心分段时单元素都装不下，导致 cnt 虚高；③ cur 与答案要用 long long（总和可达 10⁹，虽 int 勉强够但边界危险）。
互动

数列分段 · check(X) 贪心演示

候选 X
数列 [4,2,4,5,1]，m=3。选择一个候选 X，看贪心分段需要几段。
诊断

二分答案高频易错辨析

① 砍树中，若 check(H) 表示「木料 ≥ m」，那么 H 变大时？

② 数列分段的 check 里，段数计数器 cnt 初值应该是？

③ 数列分段的二分下界应取？

拿分

一道题 100 分是分档给的——不会正解也要先拿保底

复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。

第 1 档 特判 5~10 分 约 2 分钟 第 2 档 暴力 20~30 分 约 8 分钟 第 3 档 特殊性质 40~60 分 约 15 分钟 第 4 档 正解 100 分 约 25 分钟

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行， 就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

考场纪律：每档设时间上限，到点还没调通就 立刻提交当前版本，保住已有分数，再往上冲。最常见的翻车是"正解写了 50 分钟没过，连暴力分都没交上去"。
拿分

本讲 2 道题，各自的四档怎么走

伐木工人砍树 · TREE

第1档 · 2 分钟
M == 0 → 答案就是最高那棵树；M > 总长 → 0

第2档 · 8 分钟
从最高树往下逐米试，找到第一个够用的高度，maxH 小时稳过

第3档 · 10 分钟
所有树高相同 → 直接算 h − M/n

第4档 · 15 分钟
二分锯高 H，check = Σ max(0, h_i − H) ≥ M，求最大 H

数列分段 Section II · SEGMENT

第1档 · 2 分钟
M == 1 → 答案 = 总和；M == n → 答案 = 最大值

第2档 · 8 分钟
枚举答案 x 从小到大，check 用贪心分段，总和小时稳过

第3档 · 10 分钟
所有数相同 → 答案 = ceil(n/M) × a

第4档 · 15 分钟
二分答案 x，左界 max(a)、右界 sum(a)，check 贪心分段数 ≤ M

50 分钟时间盒（一题的节奏）：
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查 freopen 与文件名。
课堂上别让学生"从头想正解"。先要求每个人 15 分钟内交出第 1、2 档， 再放开冲正解。这个顺序一换，平均分通常能涨一大截——因为它杜绝了"想了 40 分钟，交上去 0 分"。
小结

本讲知识树与自检清单

🌳 知识树

识别：问「最大/最小能是多少」+ 直接求很难。

三要素：范围、单调性、check。

两问法：最大值最小化（模板①）、最小值最大化（模板②）。

复杂度：O(n log V)。

✅ 考场 N 步自检

  • 单调性方向想清楚了吗？用两个 x 手验过吗？
  • 范围下界/上界取对了吗？（极值 / 总和）
  • check 是 O(n) 吗？有没有更好的贪心？
  • 该用模板①还是②？看 check 成立时收缩哪边。
  • 需要 long long 吗？（n=10⁵、值 10⁹ 时基本都要）
  • 计数器初值对了吗？（分段题 cnt=1）
下机前：默写砍树（long long + 木料累加）与数列分段（cnt=1 + 下界取极值）。能默写 ≈ 本讲过关。

目录