Day4 二分答案学习笔记
2026-07-25 00:45:12
发布于：广东
XP02 Day4 二分答案学习笔记
课堂流程
一、从枚举答案入手
1. 什么是“答案”？
有些题目不是让我们找某个数的位置，而是让我们求一个最好的数。
比如：
伐木机的高度 H 最大是多少？
每段木头的长度 l 最大是多少？
香蕉每小时吃几根最少？
每段和的最大值最小是多少？
跳石头的最短跳跃距离最大是多少？
这些题目中，最后输出的那个数，就是我们要找的“答案”。
2. 枚举答案
如果不知道答案是多少，最笨但最容易想到的方法是：
把可能的答案一个一个试。
例如伐木题中，锯片高度可能是：
0, 1, 2, 3, ..., 最高的树
我们可以假设答案是 x，然后判断：
如果锯片高度是 x，能不能获得足够木材？
这个“判断 x 可不可以”的过程，通常写成一个函数：
bool check(long long x) {
// 判断 x 是否可行
}
3. 为什么不能一直枚举？
如果答案范围很小，枚举可以。
但如果答案范围很大，比如：
0 到 10^9
一个一个试就太慢了。
所以我们要用更快的方法：
二分答案。
二、二分答案的思路
1. 二分答案解决什么问题？
二分答案通常解决这种题：
答案是一个整数；
答案有一个范围；
我们可以判断某个答案 x 可不可行；
可行和不可行之间有明显分界线。
2. 四个固定步骤
做二分答案题，按这四步走：
第一步：确定答案范围。
第二步：写 check(x)，判断答案 x 是否可行。
第三步：根据 check(mid) 移动 l 和 r。
第四步：用 ans 记录最终答案。
3. check 函数最重要
二分答案题真正难的地方不是二分模板，而是：
check(x) 怎么写？
写 check(x) 时，要问自己：
如果答案就是 x，我怎样判断它行不行？
三、作业题目讲解
第二题：伐木工人
1. 题目要做什么？
题目已经给出锯片高度 H。
我们只需要判断：
用这个 H 去砍树，得到的木材总长度是否至少为 M。
这道题不是二分答案，而是在训练 check 思想。
2. 怎样计算木材？
对于一棵高度为 a[i] 的树：
如果 a[i] > H，可以得到 a[i] - H 米木材。
如果 a[i] <= H，得不到木材。
所以遍历每棵树，把能得到的木材加起来。
3. 判断条件
最后如果：
sum >= M
输出：
Yes
否则输出：
No
第三题：保护环境人人有责
1. 题目要做什么？
要求：
找到最大的锯片高度 H，使得获得的木材至少为 M。
高度越高，砍下来的木材越少。
高度越低，砍下来的木材越多。
所以可行情况大概是：
低高度：可行
高高度：不可行
我们要找：
最大的可行高度。
2. 答案范围
最小高度：
0
最大高度：
树的最大高度 maxh
3. check(h) 怎么写？
假设锯片高度是 h，就计算能获得多少木材。
如果：
sum >= m
说明 h 可行。
4. 边界移动
如果 check(mid) 为真：
mid 可行，记录答案，尝试更大的高度。
所以：
ans = mid;
l = mid + 1;
如果 check(mid) 为假：
mid 太高了，木材不够，只能降低高度。
所以：
r = mid - 1;
第四题：锯木材
1. 题目要做什么？
题目已经给出每段小木头的长度 l。
我们要判断：
能不能切出至少 k 段长度为 l 的木头。
这道题也是在训练 check 思想。
2. 一根原木能切几段？
长度为 a[i] 的原木，每段长度是 l，能切：
a[i] / l
这里是整数除法，剩下不够一段的部分直接丢弃。
3. 判断条件
把每根木头能切出的段数加起来。
如果：
cnt >= k
输出 Yes，否则输出 No。
第五题：光头强之单干
1. 题目要做什么？
要求：
切出至少 k 段木头时，每段木头长度 l 最大是多少。
每段越短，越容易切出足够多段。
每段越长，越不容易切出足够多段。
所以这是：
找最大的可行长度。
2. 答案范围
最小可能：
1
最大可能：
最长的原木长度 maxlen
如果连 1cm 都切不出，最后 ans 会保持为 0。
3. check(len) 怎么写？
假设每段长度是 len。
总段数：
a[1] / len + a[2] / len + ... + a[n] / len
如果总段数至少为 k，说明 len 可行。
第六题：蛋糕
1. 题目要做什么？
有 n 个长方形蛋糕，每个尺寸是 H[i] * W[i]。
要切出至少 k 块一样大的正方形蛋糕，问：
正方形边长最大是多少？
切的块越多，边长就小
切的块越少，边长就大
所以边长小了可以，但是太大就不可以
2. 一个蛋糕能切几块？
如果正方形边长是 x，一个 H * W 的长方形能切：
(H / x) * (W / x)
块正方形。
例如 6 * 5 的蛋糕，边长 2：
(6 / 2) * (5 / 2) = 3 * 2 = 6
3. check(x) 怎么写？
假设边长是 x。
统计所有蛋糕一共能切多少块。
如果：
cnt >= k
说明边长 x 可行。
第七题：梯状摆放
1. 题目要做什么？
第 1 行需要 1 个苹果。
第 2 行需要 2 个苹果。
第 3 行需要 3 个苹果。
如果摆满 x 行，一共需要：
1 + 2 + 3 + ... + x
也就是：
x * (x + 1) / 2
题目要求：
最多能摆满多少行？
2. check(x) 怎么写？
假设完整行数是 x。
如果：
x * (x + 1) / 2 <= n
说明苹果够，x 可行。
4. 为什么右边界是 2000000000？
因为：
2 * 10^9 行需要的苹果数量大约是 2 * 10^18
已经能覆盖题目中的 n <= 10^18。
第八题：爱吃香蕉的小码酱
1. 题目要做什么？
要求：
在 h 小时内吃完所有香蕉时，每小时速度 k 最小是多少？
速度越大，花的时间越少。
速度越小，花的时间越多。
所以这是：
找最小的可行速度。
2. 一堆香蕉要吃几小时？
如果这一堆有 a[i] 根，速度是 x 根/小时。
需要的小时数是：
向上取整 a[i] / x
C++ 中可以写成：
(a[i] + x - 1) / x
例如：
7 根香蕉，速度 4
(7 + 4 - 1) / 4 = 10 / 4 = 2
3. check(x) 怎么写？
假设速度是 x。
计算吃完所有香蕉需要多少小时。
如果：
time <= h
说明速度 x 可行。
第九题：鱼缸
1. 题目要做什么？
选择鱼缸高度 h。
对于每一列珊瑚：
如果 a[i] < h，需要加 h - a[i] 个单位的水。
如果 a[i] >= h，不需要加水。
最多只能用 x 个单位的水。
要求：
鱼缸高度 h 最大是多少？
2. check(h) 怎么写？
假设鱼缸高度是 h。
计算总用水量：
sum += h - a[i]，只在 a[i] < h 时加
如果：
sum <= x
说明高度 h 可行。
3. 边界移动
这题找最大高度。
如果 check(mid) 为真：
mid 可行，试试更高。
所以：
ans = mid;
l = mid + 1;
第十题：得分秘籍（上卷）
这道题不是算法题，是输出题。
注意：
题目要求输出什么，就原样输出什么。
第十二题：数列分段
1. 题目要做什么？
给一个数列，要分成 M 段。
每一段必须是连续的。
目标是：
让每段和中的最大值尽量小。
例如：
4 2 4 5 1
分成 3 段
可以分成：
[4] [2 4] [5 1]
每段和是：
4, 6, 6
最大值是 6。
2. 答案范围
答案最小不能小于：
数列中的最大值
因为每个数字必须放进某一段，如果某个数字是 5，那么最大段和至少是 5。
答案最大可以是：
整个数列的和
也就是全部放在一段里。
3. check(limit) 怎么写？
假设每段和不能超过 limit。
我们要判断：
能不能分成不超过 M 段？
注意这里是“不超过 M 段”。
因为如果最少只需要 2 段，而题目要求分成 3 段，我们可以把其中一段再拆开。
拆开后每段和只会变小，不会变大。
4. 贪心检查最少段数
为了让段数尽量少，我们从左到右放数字：
如果当前数字加入这一段后不超过 limit，就放进去。
如果加入后超过 limit，就新开一段。
这样得到的段数，就是在 limit 限制下的最少段数。
5. 边界移动
如果 check(mid) 为真：
mid 可以做到，尝试更小的最大段和。
所以：
ans = mid;
r = mid - 1;
如果 check(mid) 为假：
mid 太小，段数会超过 M，只能增大 limit。
所以：
l = mid + 1;
第十三题：跳石头
1. 题目要做什么？
有起点、终点和中间的石头。
可以最多移走 M 块中间石头。
目标是：
让相邻石头之间的最短距离尽可能大。
这句话很绕，可以拆开理解：
所有跳跃距离里，会有一个最小值。
我们希望这个最小值越大越好。
2. 答案是什么？
答案是：
最短跳跃距离。
例如某种移法后距离是：
11, 6, 4, 4
最短距离是：
4
3. 答案范围
最小可能：
1
最大可能：
L
其中 L 是起点到终点的距离。
4. check(x) 怎么写？
假设我们要求：
每次跳跃距离都至少为 x。
从起点开始看每块石头：
如果当前石头和上一块保留石头的距离 < x，这块石头不能保留，只能移走。
如果距离 >= x，这块石头可以保留。
最后统计移走了多少块。
如果：
移走数量 <= M
说明 x 可行。
5. 为什么这是贪心？
当一块石头距离太近时：
保留它会导致当前跳跃距离不够。
所以我们直接移走当前石头，让后面的距离有机会变大。
这就是按规则从左到右模拟。
6. 边界移动
如果 check(mid) 为真：
mid 这个最短距离可以做到，试试更大的最短距离。
所以：
ans = mid;
l = mid + 1;
如果 check(mid) 为假：
mid 太大了，需要移走太多石头。
所以：
r = mid - 1;
四、二分答案题目总结
1. 最大可行值题目
这类题的关键词：
最大高度
最大长度
最大边长
最大距离
尽可能大
常用边界移动：
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
对应题目：
第三题：保护环境人人有责
第五题：光头强之单干
第六题：蛋糕
第七题：梯状摆放
第九题：鱼缸
第十三题：跳石头
2. 最小可行值题目
这类题的关键词：
最小速度
最大值最小
尽可能小
常用边界移动：
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
对应题目：
第八题：爱吃香蕉的小码酱
第十二题：数列分段
3. 只写判断的题目
这类题不会让你二分，只让你判断一个给定答案可不可行。
对应题目：
第二题：伐木工人
第四题：锯木材
这两题是非常重要的基础。
因为二分答案的核心就是：
会写 check。
五、作业完成顺序建议
建议按下面顺序完成：
第二题 -> 第三题
第四题 -> 第五题
第七题
第八题
第九题
第六题
第十二题
第十三题
第十题
说明：
第二题和第四题先练 check。
第三题和第五题再把 check 放进二分。
第十二题和第十三题是重点难题，最后认真做。
六、本节课最重要的六句话
- 二分答案不是找数组位置，而是在答案范围里找最优答案。
- 做二分答案先确定答案范围。
check(x)的意思是：假设答案是x，判断它可不可行。- 找最大可行值时，
check(mid)成功就往右找。 - 找最小可行值时，
check(mid)成功就往左找。 - 数列分段和跳石头的
check都要用到贪心思想。
有帮助，赞一个