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