二分答案：猜一个答案，验证对不对——像猜硬币重量一样解决最值问题

你有没有玩过这样的游戏：老师让你猜一个1~100之间的数字，你每次说一个数，老师会告诉你“大了”还是“小了”，然后你根据提示不断缩小范围，直到猜中。二分答案的思路就和这个游戏一模一样——只不过，我们要猜的不是一个现成的数字，而是一个 可能的结果，然后通过一个“验证”的过程来判断这个结果是否合理。

有些问题直接求解很难，但如果我们能够判断“某个答案是否可行”，并且这个答案的可行性随着数值增大或减小是单调变化的（比如“长度越小越容易满足，越大越难满足”），那我们就可以用二分答案来快速找到最大可行值或最小可行值。

为什么需要二分答案？

比如，你有几根绳子，想切成若干段长度相同的小段，现在想知道每段最长能切多长。这个问题没法直接用公式算出来，但我们可以反过来想：如果我们猜一个长度，很容易验证能不能切出指定段数。而且长度越小越容易切够段数，长度越大越难。所以我们可以用二分法不断尝试，最终找到那个“临界值”。

这种思路叫做 二分答案 + 验证，是竞赛里处理“最值问题”的经典套路。

二分答案的两个核心条件

1. 答案有范围：我们能确定答案的最小可能值（left）和最大可能值（right）。
2. 答案具有单调性：存在一个分界点，使得小于该点的所有答案都可行（或都不可行），大于该点的则相反。通常题目会说明“越……越容易”。

例如，切绳子问题中，长度越小，切出的段数越多，越容易达到要求的k段；长度越大，段数越少，越难达到。这就是“越小越可行，越大越不可行”的单调性。

二分答案的步骤

1. 确定答案的搜索区间：left 和 right。比如绳子长度 left = 0（最小可能），right = 最长绳子的长度。
2. 每次取区间中点 mid：mid = (left + right) / 2。
3. 写一个验证函数，判断 mid 是否可行。例如切绳子：检查用当前长度 mid 能不能切出至少 k 段。
4. 根据验证结果调整区间：
   • 如果 mid 可行，说明答案可以更大（或更小，取决于单调性），所以把 left 移到 mid（或 right 移到 mid）。
   • 如果 mid 不可行，则把另一端点移过来。
5. 重复直到区间足够小（整数问题可以 left+1 == right 时结束，浮点数问题可以迭代固定次数或按精度）。

验证函数——整个方法的灵魂

验证函数是二分答案的关键，它必须 高效 且 正确。对于不同类型的题目，验证方法各不相同，常见的有贪心、模拟、动态规划等。

比如切绳子问题，验证函数非常简单：遍历每根绳子，用整根长度除以目标长度，累加能切的段数，最后判断总段数是否 ≥ k。这个过程是 O(n) 的，很快。

再比如，你要判断一个同学能否在限定时间内做完所有暑假作业，就可以模拟每天做多少页，看是否能在截止日前完成。这种验证往往就是一个暴力模拟或贪心策略。

新手容易犯的三个错误

1. 验证函数没写对：验证的结果必须和单调性一致。比如切绳子，验证函数返回“切出的段数 >= k”，而不是“== k”。因为“>=k”意味着可行，而“正好等于k”可能因为浮点误差无法恰好得到。
2. 二分范围不对：left 和 right 的初值要包含所有可能的答案。比如绳子长度，left 不能设成 1，因为可能最小长度接近 0；right 要取最长绳子长度，而不是绳子总长。
3. 浮点数精度控制不足：对于浮点数答案，通常用固定次数的二分（比如 100 次）来保证精度，而不是用 while left < right 这种条件，因为浮点数比较可能陷入死循环。

完整示例：切绳子问题（完整代码）

下面是一个可运行的 Python 程序，解决“把 n 段绳子切成 k 段长度相同的小段，求每段最大可能长度”的问题。代码中保留了原来的核心函数，并补充了输入输出和注释。

def can_cut(ropes, length, k):
    """判断能否切出k段长度>=length的绳子"""
    count = 0
    for rope in ropes:
        count += rope // length   # 每根绳子能切出几段
    return count >= k

def max_rope_length(ropes, k):
    """返回最大可能的切割长度（精确到0.01）"""
    left = 0.0                 # 最小可能长度
    right = max(ropes)         # 最大可能长度（最长的一根绳子）
    # 二分浮点数：迭代100次，精度远高于0.01
    for _ in range(100):
        mid = (left + right) / 2
        if can_cut(ropes, mid, k):
            left = mid         # 可以切，尝试更大长度
        else:
            right = mid        # 不能切，减小长度
    return left

# 测试数据
ropes = [8.02, 7.43, 4.57, 5.39]   # 四根绳子的长度
k = 11                               # 要切成11段
result = max_rope_length(ropes, k)
print(f"每段最大长度约为：{result:.2f}")   # 输出保留两位小数

运行结果：每段最大长度约为：2.01

如果你想验证一下：用 2.01 切，8.02 可以切 3 段（8.02//2.01=3），7.43 切 3 段，4.57 切 2 段，5.39 切 2 段，合计 10 段，不足 11 段；而用 2.00 切，8.02 切 4 段，7.43 切 3 段，4.57 切 2 段，5.39 切 2 段，合计 11 段，正好可行。所以最大长度是 2.00 附近，程序输出 2.01 是因为二分迭代了 100 次，接近但不等于精确值（实际精确值为 2.00）。

更多生活中的例子

• 零花钱分配：你每周有 100 元，要买 a 件 T 恤（每件 x 元）和 b 本笔记本（每本 y 元），T 恤价格越贵能买的数量越少，你能找出 T 恤的最高价格吗？可以二分价格，验证：买完 a 件 T 恤后剩下的钱是否足够买 b 本笔记本。
• 考试分数线：某个比赛获奖人数有限，主办方要划一条分数线，分数越高，过线的人越少。已知每个人分数，问最高分数线能使获奖人数不超给定值？二分分数线，验证：统计分数 ≥ 分数线的人数。
• 排队等位：餐厅有 n 个桌子，每个桌子可坐不同人数，现在来了 m 个人，问最少需要等待多少分钟才能全部坐下（假设每分钟翻桌一次）？这其实是一个调度问题，也可以用二分答案猜时间，然后验证该时间内能否服务完所有客人。

相关指引

二分答案并不孤立，它经常和以下知识点一起出现：

• 二分查找：在有序数组中找元素，是二分答案的“兄弟”。二分答案本质上也是在“有序”的答案空间里进行查找，只不过这个有序性是由题目条件保证的，而不是数组本身。
• 贪心算法：验证函数中经常用到贪心策略（比如切绳子就是最简单的贪心：每根绳子能切多少就切多少）。
• 模拟：对于复杂过程，验证函数可能需要完整模拟一遍（例如调度问题）。
• 整数二分和浮点数二分：整数二分要注意边界和死循环（一般用 while left < right 配合 mid = (left + right) // 2 或 mid = (left + right + 1) // 2 两种模板）；浮点数二分则常用固定次数二分。

掌握了二分答案，你就能解决一大批“最大值最小”或“最小值最大”的题型，比如“分巧克力”、“木材切割”、“跳石头”、“借教室”等经典题目，它们都是 CSP-J 和 NOIP 的常客。