别再死记硬背二分模板了！用‘买饮料’和‘砍树’两道题，带你彻底搞懂二分答案的Check函数怎么写

二分答案实战：从买饮料到砍树，掌握Check函数的设计精髓

算法竞赛中，二分查找是每个选手必备的基础技能。但真正让初学者头疼的，往往不是二分模板本身，而是那个神秘的Check函数——它决定了二分能否正确工作，却总是让人无从下手。今天我们就用两个生活化的例子，彻底拆解Check函数的设计逻辑。

1. 为什么二分答案的关键在于Check函数？

二分查找看似简单，但应用到实际问题时，模板代码往往帮不上忙。核心难点在于：如何判断中间值是否符合条件？这就是Check函数的职责。

想象你在玩猜数字游戏，对方告诉你"大了"或"小了"，这就是最朴素的Check函数。但在算法题中，这个判断过程可能非常复杂。以买饮料问题为例：

小明想60天每天喝一瓶饮料，每买1瓶得1个瓶盖，5个瓶盖可换1瓶。饮料3元/瓶，最少要花多少钱？

常规解法需要复杂的数学推导，而二分答案的思路是：假设购买x瓶，判断是否能喝够60天。这个判断过程就是Check函数。

def check(x): bottles = x caps = x while caps >= 5: new = caps // 5 bottles += new caps = caps % 5 + new return bottles >= 60

这个Check函数的精妙之处在于：

1. 模拟了瓶盖兑换的过程
2. 最终返回是否满足需求
3. 完全独立于二分查找的主逻辑

2. 买饮料问题：Check函数的模拟艺术

让我们深入分析买饮料的Check函数。这个问题的难点在于瓶盖兑换的循环过程——新换的饮料又会产生瓶盖，可能引发连锁兑换。

Check函数的编写步骤：

1. 初始化状态：购买的x瓶同时产生x个瓶盖
2. 兑换循环：只要瓶盖≥5就继续兑换
   • 计算可兑换的新饮料数
   • 更新总饮料数和剩余瓶盖数
3. 终止条件：当瓶盖不足5时结束
4. 结果判断：总饮料数是否≥60

# 更详细的Check函数实现 def check(x): total = x # 总饮料数 caps = x # 当前瓶盖数 while True: exchanged = caps // 5 # 本次兑换的饮料 if exchanged == 0: break total += exchanged caps = caps % 5 + exchanged # 剩余瓶盖+新饮料的瓶盖 return total >= 60

这个例子展示了Check函数的典型特点：将问题转化为可计算的模拟过程。在二分查找的每次迭代中，Check函数都独立完成一次完整的模拟验证。

3. 砍树问题：Check函数的数学转化

再看另一个经典问题——砍树：

有N棵树，需要得到至少M米的木材。可以将锯片设定到任意高度，所有高于此高度的树会被锯掉顶部。求锯片的最大高度。

这个问题需要逆向思考：设定一个高度h，计算能得到多少木材。Check函数的核心就变成了数学计算：

def check(h): total = 0 for tree in trees: if tree > h: total += tree - h return total >= M

与买饮料问题不同，这里的Check函数：

1. 不需要循环或复杂的状态维护
2. 通过简单的数学计算即可得出结论
3. 体现了二分答案问题的多样性

4. Check函数设计的通用方法论

通过以上两个例子，我们可以总结出Check函数的设计模式：

4.1 问题转化三步骤

1. 确定验证目标：明确要验证的假设是什么（如"购买x瓶是否足够"）
2. 建立计算模型：设计算法计算假设条件下的结果
3. 设定判断标准：确定什么情况下假设成立

4.2 常见Check函数类型

4.3 调试Check函数的技巧

1. 边界测试：检查最小/最大输入值
2. 中间输出：在关键步骤打印变量值
3. 手动验证：用简单案例手工计算对比
4. 时间复杂度：确保不会成为性能瓶颈

# 带调试输出的Check函数 def check_debug(x): bottles = caps = x step = 0 print(f"初始: 购买{x}瓶, 瓶盖{caps}") while caps >= 5: exchanged = caps // 5 bottles += exchanged new_caps = caps % 5 + exchanged step += 1 print(f"第{step}次兑换: 得{exchanged}瓶, 总{bottles}瓶, 剩余瓶盖{new_caps}") caps = new_caps result = bottles >= 60 print(f"最终: {bottles}瓶, 需求{60}, 结果{'满足' if result else '不满足'}") return result

5. 避开Check函数的常见陷阱

即使理解了原理，实践中仍容易犯错。以下是几个常见问题：

5.1 循环终止条件错误

在买饮料问题中，如果错误地写成：

while caps > 0: # 错误！应该用 caps >= 5 exchanged = caps // 5 ...

会导致无限循环，因为最后可能有1-4个瓶盖无法兑换但循环不终止。

5.2 整数溢出问题

当处理大数时，中间结果可能溢出。例如砍树问题的木材总量：

total = 0 for tree in trees: total += tree - h # 如果tree很大且数量多，可能溢出

解决方案是提前终止：

total = 0 for tree in trees: total += tree - h if total >= M: # 提前达到目标就返回 return True

5.3 浮点数精度问题

对于浮点数二分，Check函数要特别注意精度：

# 银行贷款问题的Check函数 def check(rate): balance = w0 for _ in range(m): balance = balance * (1 + rate) - w if balance < 0: # 提前还清 return False return balance >= 0 # 注意浮点数比较可能有问题

更好的写法是设定精度阈值：

return abs(balance) < 1e-6 or balance > 0

6. 从例题到竞赛：Check函数的进阶技巧

掌握了基础后，来看一些优化技巧：

6.1 预处理优化

在某些问题中，可以对数据预处理加速Check。例如"进击的奶牛"问题：

x.sort() # 预处理排序 def check(d): last = x[0] count = 1 for pos in x[1:]: if pos - last >= d: last = pos count += 1 if count >= C: return True return False

6.2 早期终止

当Check过程可以提前得出结论时，立即返回：

# 木材加工问题 def check(L): count = 0 for piece in pieces: count += piece // L if count >= k: # 提前达到目标 return True return False

6.3 记忆化搜索

对于重复计算的情况，可以使用缓存：

from functools import lru_cache @lru_cache(maxsize=None) def check(x): # 复杂计算过程 ...

7. 综合训练：设计你自己的Check函数

现在让我们尝试一个稍复杂的问题——"跳石头"：

河道中有N个石头，位置已给出。最多移走M个石头，求最小跳跃距离的最大值。

Check函数的设计思路：

1. 验证目标：判断在给定跳跃距离d下，是否可以通过移走≤M块石头满足条件
2. 计算模型：模拟跳跃过程，统计需要移走的石头数
3. 判断标准：需要移走的石头数≤M

def check(d): removed = 0 last = 0 # 起点位置 for stone in stones: if stone - last < d: removed += 1 if removed > M: return False else: last = stone return True

这个Check函数展示了如何将问题转化为贪心验证，是二分答案中常见的模式。

8. 二分查找与Check函数的协同优化

最后要注意二分查找的实现与Check函数的配合：

1. 整数二分的两种模式：

   • 找最小满足值（左边界）

   while left <= right: mid = (left + right) // 2 if check(mid): right = mid - 1 else: left = mid + 1 return left

   • 找最大满足值（右边界）

   while left <= right: mid = (left + right) // 2 if check(mid): left = mid + 1 else: right = mid - 1 return right

2. 浮点数二分的特殊处理：

   while right - left > 1e-6: mid = (left + right) / 2 if check(mid): left = mid else: right = mid return left

记住：二分查找控制搜索方向，Check函数决定搜索条件，两者配合才能高效解决问题。