PYTHON LESSON 076
例题精练：跳石头分步拆解
拆解经典二分答案题“跳石头”，掌握“发现单调性 → 写 check → 套二分框架”的解题套路。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 答案单调：距离要求越大越难满足
- check 贪心：太近就搬走，统计搬走数量
- 别忘了最后一块石头到终点的距离
01 · 核心概念
“最短距离最大化”的二分答案 + 贪心检验
“最短距离最大化”的二分答案 + 贪心检验：起点在 0、终点在 L，石头排在河中间。至多搬走 m 块，让剩下的相邻间距里最短的那个尽量大。先问自己：直接求最大值好求吗？不好求——但检验“最短距离能不能达到 x”很好写。
GESP Python 5 级 · 二分答案GESP Python 5 级 · 贪心算法复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
答案单调：距离要求越大越难满足先准确读出这条写法的结构与作用。
check 贪心：太近就搬走，统计搬走数量换一组最小数据，手工推演一次结果。
别忘了最后一块石头到终点的距离再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 例题精练：跳石头（考级模拟卷 A2 题解）
L, n, m = map(int, input().split())
rocks = list(map(int, input().split()))
def check(x):
"""移走至多 m 块石头，能否让每段跳跃都不小于 x"""
removed = 0
last = 0 # 上一块保留的位置（起点）
for r in rocks:
if r - last < x: # 离上一块太近，搬走它
removed = removed + 1
else:
last = r
if L - last < x: # 最后一段到终点也要够长
return False
return removed <= m
left, right = 1, L
ans = 0
while left <= right:
mid = (left + right) // 2
if check(mid): # 可行，尝试更大的距离
ans = mid
left = mid + 1
else: # 不可行，只能缩短要求
right = mid - 1
print(ans)4
假设输入为题面样例：第一行 25 5 2，第二行 2 11 14 17 21。搬走 2 和 14 两块后，间距为 11、6、4、4，最短距离恰为 4。
04 · 逐步理解
每一步只解决一个问题
- 01
第一步：读懂题意
起点在 0、终点在 L，石头排在河中间。至多搬走 m 块，让剩下的相邻间距里最短的那个尽量大。先问自己：直接求最大值好求吗？不好求——但检验“最短距离能不能达到 x”很好写。
- 02
第二步：发现单调性
要求的最短距离 x 越大，要搬走的石头越多，超过 m 就办不到。x 可行，比 x 小的都可行——这就是单调性，二分答案的通行证到手了。
- 03
第三步：写 check(x)
贪心扫描一遍：last 记录上一块保留的位置，当前石头离它不足 x 就搬走、计数加一；够 x 就保留并更新 last。最后看搬走总数是否不超过 m。
if r - last < x: removed = removed + 1 else: last = r - 04
第四步：别忘最后一段
循环只管了石头之间的间距，最后一块保留的石头到终点 L 的距离也必须 ≥ x，否则照样不合格。这个隐藏边界是本题最常见的丢分点。
if L - last < x: return False - 05
第五步：套二分框架
下界取 1、上界取 L。check(mid) 可行就记下 mid、抬下界试更大的；不可行就压上界。循环结束时，ans 就是“最短距离的最大值”。
if check(mid): ans = mid left = mid + 1 else: right = mid - 1 - 06
第六步：验证与复盘
样例 25 5 2 应输出 4：搬走 2 和 14 后间距为 11、6、4、4。再把 m 改成 3，石头全搬走，答案应是 L 本身 25。复盘“单调性 → check → 框架”三步，这类题就彻底通了。
05 · 练习与检验
自己写出来，才算真正学会
- 1读题，用样例在纸上画出石头位置
- 2手推：移走 2 块后最短跳跃距离怎么算
- 3运行题解，验证样例输出 4
- 4把 m 改成 3，先预测答案再运行验证
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
程序组织类、对象、属性与方法理解对象模型和封装边界，用类表达有状态的实体，而不是把所有程序都强行改成类。＋
正式定义
类描述一类对象的数据与行为；实例是类创建的具体对象。实例方法的第一个参数通常命名为 self，用来访问当前实例；__init__ 在实例创建后负责初始化状态。
必须掌握
- 实例属性通常在 __init__ 中通过 self.name = value 建立。
- 实例方法通过 object.method() 调用；Python 会自动把实例绑定给 self。
- 类属性由实例共享，实例属性属于单个对象；同名实例属性会遮蔽类属性。
- __repr__ 面向开发与调试，__str__ 面向用户显示；特殊方法应遵守其协议。
- 继承表达“是一种”关系，组合表达“拥有一个”关系；能用组合清晰表达时不要滥用继承。
- 对象相等默认仍是身份比较；需要按内容相等时要定义相应协议。
常见误区
- 在方法中漏写 self
- 把每个实例独有的可变数据写成类属性
- 只为包装几个无状态函数而建类
- 继承层次过深导致行为难以追踪
适用边界
- 课程使用普通类解释对象模型；dataclass、property、抽象基类和元类是后续工程工具。
- 算法题常用函数和基本容器更直接，不要求为了“面向对象”而增加结构。
完成检查