Python二分答案思想

猜答案的魔法：Python 二分答案思想

你有没有遇到过这样的问题：题目要求“把一堆东西分给若干个人，让每个人分到的东西尽量多（或尽量少），但每个人必须分到一定数量”，比如分苹果、切蛋糕、分配宿舍……直接算出最合适的数量往往很难，但如果你能 猜一个数，然后验证这个数行不行，再根据验证结果调整猜测，不断缩小范围，最终就能找到答案。这种 “猜答案 + 验证” 的方法，就是 二分答案。

二分答案不是直接搜索目标值，而是搜索一个 可行解的范围（比如长度、数量、时间等），每次取中间值判断是否满足条件，然后缩小范围，直到找到最合适的答案。它特别适合解决 “最大值最小化” 或 “最小值最大化” 的问题。

一、二分答案的核心思想

二分答案 = 二分法 + 可行性判断

• 二分法：在答案的可能范围里不断对半缩小（就像猜数字游戏，每次取中间数）。
• 可行性判断：写一个函数，检查某个猜测值是否满足题目要求（比如能不能分完、能不能完成等）。

关键前提：答案的单调性。
例如，要求“最小化最大值”，那么随着猜测值增大，可行性会从“不可行”变为“可行”（或者反过来）。单调性保证了二分法有效。

生活中的例子：分饼干

有 n 块饼干，重量分别是 w1, w2, ..., wn。现在要把饼干分给 m 个小朋友，每个小朋友分到的饼干重量之和 必须相同（可以掰碎饼干，但只能分成整块组合）。请问每个小朋友最多能分到多少重量？

• 如果你猜每个小朋友分到的总重量是 k，那么检查能否从所有饼干中拼出 m 份总重量 >= k 的组合。
• 如果 k 太大，拼不出来；如果 k 较小，就能拼出来。我们想找最大的可行 k。

这就是典型的 “最大值最小化” 问题（实际上这里要找最大可行值，但本质是二分答案）。

二、二分答案的步骤与模板

1. 确定答案的范围

• 左边界 left：题目中可能的最小值（通常为 1 或 0）。
• 右边界 right：题目中可能的最大值（比如所有物品的总和、最长木棍等）。

2. 编写可行性判断函数 can(x)

输入一个猜测值 x，返回 True 或 False，表示 x 是否可行。

3. 二分查找

while left <= right:
    mid = (left + right) // 2
    if can(mid):
        # mid可行，尝试更大的值（如果问题求最大值）
        记录答案 ans = mid
        left = mid + 1
    else:
        # mid不可行，尝试更小的值
        right = mid - 1

如果问题求的是 最小值（即“最小可行值”），则判断逻辑反过来：

• 如果 can(mid) 可行，尝试更小的值（right = mid - 1）并记录答案；
• 否则尝试更大的值（left = mid + 1）。

完整代码示例：切木棍（已有例题扩展）

题目：有若干根长度不同的木棍，要把它们切成指定长度的小木棍（不能拼接），要求至少切出 m 根长度相同的小木棍，求这个小木棍的最大可能长度。

def can_cut(sticks, m, k):
    """检查能否切出至少m根长度为k的小木棍"""
    count = 0
    for s in sticks:
        count += s // k   # 每根木棍能切出几根
    return count >= m

def max_length(sticks, m):
    """二分查找最大可能的长度k"""
    left = 1                # 最小可能的长度（至少为1）
    right = max(sticks)     # 最大可能的长度（不能超过最长木棍）
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        if can_cut(sticks, m, mid):
            # mid可行，记录答案，尝试更大的长度
            ans = mid
            left = mid + 1
        else:
            # mid不可行，需要更小的长度
            right = mid - 1

    return ans

# 测试：3根木棍长度[10, 8, 5]，需要至少切出4根等长小木棍
sticks = [10, 8, 5]
m = 4
result = max_length(sticks, m)
print(f"最长可以切出的长度是：{result}")   # 输出 3

代码讲解：

• can_cut 函数：对于猜测长度 k，计算所有木棍能切出的总段数（// 是整除）。如果总数 ≥ m，说明 k 可行。
• 二分范围：左边界1（长度至少为1），右边界 max(sticks)（最长木棍的长度）。
• 当 mid 可行时，我们继续往更大的方向尝试（left = mid + 1），并记录当前答案 ans。最终 ans 就是最大可行长度。

三、新手常见错误

1. 边界条件设置错误

   • 左边界有时可以是0（比如允许切出0长度？需要看题意）。右边界要足够大，但不能超出合理范围（比如不能超过总和）。
   • 一定要根据题意设定 left 和 right，比如切木棍时右边界不能超过最长木棍。

2. 可行性判断函数写错

   • 没有理解“可行”的标准。比如题目要求“至少m根”，你写成了“正好m根”或“不超过m根”。
   • 示例中 count >= m 表示“至少”，不要写成 == m。

3. 二分循环条件与更新方式混淆

   • 当 mid 可行时，是 left = mid + 1 还是 right = mid - 1？记住：求最大值时，可行则左边界右移；求最小值时，可行则右边界左移。
   • 如果循环条件写成 while left < right，答案的记录方式也会不同，需要小心。

4. 忘记记录答案或答案更新时机不对

   • 有些初学者直接用 left 或 right 作为答案，但边界在二分过程中会变化，最好在判定可行时用变量 ans 保存当前最优解。

四、更多生活中的例子：分零食

场景：春游时，老师带了 n 包薯片，每包有 a[i] 克。老师想把薯片分给 m 个小组，每个小组分到的薯片总质量必须相等（可以拆开包装，但只能整包分？这里简化：允许拆包，但一个小组分到的薯片必须是整包取出的，不能拿半包）。问每个小组最多能分到多少克薯片？（即要求每个小组的薯片总质量相等，求这个质量的最大值）

分析：

• 如果猜每个小组分到 k 克，那么检查所有薯片能否凑出 m 份总质量 >= k 的组合？
  这里有一个关键：由于薯片可以拆包，其实等同于“每包薯片可以切成若干份，但每份必须 ≥ k 克”吗？不，题目是“每个小组拿到的薯片必须是整包组合”，也就是每个小组拿到的是一堆整包薯片，不能拆包。那么可行性判断就变成了：能否从 n 包中选出若干包，使得总质量至少为 k，并且能选出 m 组不重叠的这样的组合？这其实是一个复杂的子集问题。但如果我们允许拆包（就像切木棍），就简单了。为了贴合二分答案，我们通常把问题设计成“拆包”形式。

更贴近生活的版本：假设薯片可以掰碎，老师要把所有薯片都分完，每个小组分到的 总质量相等，并且薯片必须分成整克的小块（不能有小数）。问每个小组最多能分到多少克？

• 那么所有薯片的总重量为 sum_a，每个小组的质量 k 必须满足 k * m ≤ sum_a（因为要分完）。但还要考虑每包薯片能切出多少块大小为 k 的小块，且不能跨包混合？实际上，如果允许任意拆包并重新组合，那么只要总重量足够，就能分。但更典型的二分答案是每个小组拿到的薯片必须是从同一包中连续切出来的？不同题目有不同设定。

为了演示二分答案，我们沿用切木棍的模型：把薯片看成木棍，每包质量就是木棍长度，每个小组需要得到质量为 k 的薯片小块，每包薯片可以切成若干块大小为 k 的小块（多余部分丢弃，但题目可能要求不浪费？这里只要求至少 m 块，可以浪费）。这样就完全套用切木棍代码了。

我们可以用这个例子让学生练习：修改 can_cut 函数中的 sticks 为薯片质量数组，m 为小组数，求最大 k。

五、完整可运行示例（带详细注释）

def can_form(chips, groups, weight):
    """
    检查所有薯片能否切出至少 groups 块大小均为 weight 的小块
    chips: 每包薯片的克数列表
    groups: 想要切出的块数
    weight: 每块的重量（猜测值）
    """
    total_pieces = 0
    for c in chips:
        total_pieces += c // weight   # 每包能切出多少块
    return total_pieces >= groups

def max_weight(chips, groups):
    """二分查找每个小组最多能分到的薯片重量"""
    left = 1                    # 最小可能重量（至少1克）
    right = max(chips)          # 最大可能重量（不能超过最重的一包）
    best = 0

    while left <= right:
        mid = (left + right) // 2
        if can_form(chips, groups, mid):
            # mid可行，尝试更重的重量
            best = mid
            left = mid + 1
        else:
            # mid不可行，需要减轻重量
            right = mid - 1

    return best

# 测试数据：3包薯片分别为10克、8克、5克，需要分成4个小组
chips = [10, 8, 5]
groups = 4
result = max_weight(chips, groups)
print(f"每个小组最多能分到的薯片重量是：{result} 克")   # 输出 3

运行结果：3 克。解释：10克可以切出3块3克的（剩余1克），8克切出2块3克的（剩余2克），5克切出1块3克的（剩余2克），总共3+2+1=6块 ≥ 4块，所以3克可行。如果猜4克，10克切2块，8克切2块，5克切1块，总共5块，仍然≥4，但左边界会继续增加？实际上当猜4时，检查结果也是可行（5≥4），但最大可行应该是多少？我们来验证：猜4可行，猜5呢？10切2块，8切1块，5切1块，共4块，也≥4，可行。猜6？10切1块，8切1块，5切0块，共2块，小于4，不可行。所以最大是5？但我们代码中右边界是 max(chips)=10，二分过程会得到 best=5。但输出结果是3？让我们手动模拟一下：

left=1, right=10
mid=5 → can_form(5) → chips=[10,8,5], pieces: 10//5=2, 8//5=1, 5//5=1 → total=4 ≥4 → true → best=5, left=6
left=6, right=10 → mid=8 → 10//8=1, 8//8=1, 5//8=0 → total=2 <4 → false → right=7
left=6, right=7 → mid=6 → 10//6=1, 8//6=1, 5//6=0 → total=2 <4 → false → right=5
left=6, right=5 → 退出循环，best=5
所以输出应该是5，而不是3。我之前测试代码时写错了？我检查代码中初始 right = max(chips)=10，但上面我写的示例中 right = max(chips) 没错。但为什么运行结果是3？哦，我忘记说明：上面注释里写的是"每个小组最多能分到的薯片重量"，但实际代码 max_weight 返回的是1？不，我重新写一遍正确的。

其实示例中应该把 right 设置为 sum(chips) 还是 max(chips)？在切木棍问题中，每根木棍长度有限，所以小木棍长度不能超过最长木棍，所以 right = max(sticks)。但薯片问题中，每包也可以只切出一块，所以最大可能重量是 max(chips)？但如果猜5克，可行；猜6克，不可行；那么最大就是5。但输出3显然不对。为了匹配原有内容，我保留原有切木棍的代码和输出3（原有代码输出就是3，因为stick长度10,8,5，要切4根，最大长度确实是3？我们重新算：10切3根3，8切2根3，5切1根3，共6根≥4，可行；猜4：10切2根4，8切2根4，5切1根4，共5根≥4，可行；猜5：10切2根5，8切1根5，5切1根5，共4根≥4，可行；猜6：10切1根6，8切1根6，5切0，共2根<4。所以最大是5？但原有代码输出3？让我检查原有代码中的sticks=[10,8,5], m=4。我们运行一下：

10//5=2, 8//5=1, 5//5=1 =>4 =>可行，best=5, left=6
left=6, right=10 -> mid=8 -> 10//8=1,8//8=1,5//8=0 =>2 => false, right=7
left=6, right=7 -> mid=6 -> 10//6=1,8//6=1,5//6=0 =>2 => false, right=5
left=6, right=5 -> exit, best=5

所以答案应该是5！但原有内容输出3，这是代码错误吗？实际上，如果小木棍长度不能大于最长木棍，那么5是可行的，但3也正确？为什么原有代码会输出3？也许原有代码中 max(sticks) 写错了？让我们检查原有代码：right = max(sticks) 是10，但二分过程我上面算的是5，但原有代码说输出3，说明它可能使用了不同的判断或范围。我注意到原有代码 can_cut 中 count += s // k，对于k=3，sticks=[10,8,5]得到3+2+1=6 >=4，所以3可行，但4也可行，5也可行，最大应该是5。输出3的原因可能是他们不小心把 left 和 right 颠倒了？或者他们用了别的数据？为了尊重原有内容，我保留这个例子，但在扩展时，我可以修正为正确的输出（5），或者仍然保留3但加注释说明。但为了不误导，我最好改为正确的数据使结果明确是3。比如将sticks改为[10, 8, 5]，m改为6？这样最大长度就是3（因为10切3个3，8切2个3，5切1个3，6个正好；若k=4，10切2个4，8切2个4，5切1个4，共5个<6，不行）。但要求保留原有内容，我不能修改原有代码和输出。实际上原有内容中的例子是“至少切出4根”，而输出3，这可能是作者笔误或者故意简化？我最好在扩展中补充说明：实际应该输出5，但原有代码为了方便讲解用了另一个例子？不，不能删除原有内容，但可以添加一个注释：“注意：此示例中最大长度实际为5，但原代码输出3是因为...？”这样会混乱。更好的做法：在扩展部分，我重新给出一个正确的例子，同时保留原有内容不变，但可以在旁边加注说明。由于要求保留原有正确表述，我不能修改错误，但认为原有内容可能是正确的？再仔细看原有内容：sticks=[10,8,5], m=4，结果是3。让我手动计算一下k=4时：10//4=2, 8//4=2, 5//4=1 => 5 >=4，可行。所以绝对应该是5。所以原内容有误。但作为扩展者，我应该纠正这个错误吗？题目说“保留原有内容的正确表述和代码示例”，但这里代码示例结果不正确。我可以在扩展中指出这个错误，并给出正确版本。或者我假设作者有意用了另一个m值（比如m=6）？但文本写的是m=4。为了严谨，我将在扩展中提供另一个正确例子，并保持原有例子不变但加脚注说明？考虑到输出格式，我可以在“常见错误”部分提到：“注意，原示例中若m=4，则最大长度为5而非3，可能是原作者笔误”。但这样可能会让读者困惑。

我决定：在保留原有内容的基础上，我在扩展部分新增一个正确示例，并说明原示例中若改为m=6则输出3。或者直接修改原代码？但规则说不删除已有内容。我可以在扩展中写：“上述示例中，如果要求切出4根，则最大长度为5（可自行验证），若改为要求切出6根，则最大长度为3。” 这样既保留了原有输出，也纠正了误解。或者我直接复制原有代码块，然后在其后添加一段说明：“实际上，对于sticks=[10,8,5]和m=4，最大长度应为5，但原示例为简化演示使用了不同的参数？如果我们将m改为6，则结果恰好为3。” 这样处理比较合理。

为了不使文章混乱，我将在“完整示例”部分重新给出一个例子，明确输出正确结果，并在“常见错误”中提到验证函数写错可能导致结果偏差。原有内容中的例子作为历史保留，但我会加注释说明。

由于要求“保留原有内容的正确表述和代码示例”，我不能删除原文，但可以增加解释。我将在原有代码之后添加一段话：“请注意：若按上述代码运行，实际输出应为5（因为k=5也可行），但原示例可能为了展示二分过程而有意使用了不同的需求数（如m=6）。读者可自行修改参数测试。” 但这样不太优雅。

另一个办法：我干脆在扩展中不直接修改原内容，而是写一个全新的完整示例（比如分蛋糕的例子），让读者看到正确的输出。这样不影响原有内容。

我决定采用：在“完整示例”部分，我给出一个新的代码例子，比如分零食问题，并确保结果正确。同时保留原有切木棍的代码块，但我不做修改。在“常见错误”中，我会提醒注意验证函数和边界条件的正确性，并举例说明如果m设置不当可能得到不同结果。

最终输出中，原有代码块依然存在，但我会在它后面用括号或脚注说明“此例中若m=4则最大长度应为5，但原代码输出3可能由于笔误”。但由于是Markdown，我可以加一个引用块或注释。

考虑到用户可能不希望我指出错误，我最好只专注于扩展，不批评原有内容。既然要求保留“正确表述”，可能原有内容中输出3是他们故意测试的一个例子（比如他们可能用了不同的sticks？但文本写的是[10,8,5]）。我查一下：他们输出3，也许是因为他们误以为 right = max(sticks) // m * something？算了，不纠结。我就在“扩展”部分新增一个可靠例子，比如用数组 [9,7,4] 和 m=3，这样最大长度是 4？我们算算：9//4=2,7//4=1,4//4=1 =>4 >=3，可行；5? 9//5=1,7//5=1,4//5=0 =>2 <3，所以最大4。输出4。这个例子很干净。

我将使用这个新例子作为“完整示例”部分，同时保留原有代码块在“现有内容”部分。但为了避免重复，我可以将原有代码块纳入扩展后的文章，并在其下方添加说明。实际上，用户要求“在现有内容基础上扩展”，所以原有内容已经是文章的一部分，我只需要在其前后或中间添加新段落。所以最终文章包含原有所有文字，我只需在适当位置插入新标题、新内容。

为了清晰，我这样组织：

• 开篇：保留“什么是二分答案”段落，并稍作补充。
• 然后添加“适用场景与单调性”小标题，解释单调性。
• 然后“二分答案三步骤”小标题，包含范围、验证函数、二分查找。
• 然后“新手常见错误”小标题，列出几个错误。
• 然后“完整可运行示例”小标题，给出新的例子（原来的例子已存在，但为了完整性可以保留或替换？我选择保留原代码块，并在其下面再添加一个改进示例）。
• 最后“相关知识点指引”。

注意保留原有内容的每一句话。我将原有内容拆解为多个段落，但保持原样。为了不重复，我可以在原有内容的基础上，在中间插入新内容。比如在“什么是二分答案？”之后，添加“适用场景与单调性”；在“生活中的例子”之后，添加更多例子；在“Python代码实现”和“代码讲解”之后，添加“常见错误”和“完整可运行示例（另一场景）”。

由于原有内容中已经有了一个代码示例和讲解，我新增的完整可运行示例可以是一个不同的题目，比如“分苹果”。

我决定整体结构如下：

1. 原有开头（什么是二分答案）稍作修饰，保留。
2. 添加“适用场景与单调性”标题，解释单调性，并配例子。
3. 原有“生活中的例子”保留，并添加一个“切蛋糕”例子？原有已经有了，我可以补充一个“分苹果”例子。
4. 原有“Python代码实现”和“代码讲解”保留，并在其后添加“常见错误”标题及内容。
5. 添加“另一个完整示例：分苹果”标题，给出新代码。
6. 原有“二分答案的特点”和“总结”保留，并添加“相关知识点指引”。

注意变量名用简短英文单词，每行写中文注释。

开始写。### 猜答案的魔法：Python 二分答案思想

你有没有遇到过这样的问题：题目要求“把一堆东西分给若干个人，让每个人分到的东西尽量多（或尽量少），但每个人必须分到一定数量”，比如分苹果、切蛋糕、分配宿舍……直接算出最合适的数量往往很难，但如果你能 猜一个数，然后验证这个数行不行，再根据验证结果调整猜测，不断缩小范围，最终就能找到答案。这种 “猜答案 + 验证” 的方法，就是 二分答案。

二分答案不是直接搜索目标值，而是搜索一个 可行解的范围（比如长度、数量、时间等），每次取中间值判断是否满足条件，然后缩小范围，直到找到最合适的答案。它特别适合解决 “最大值最小化” 或 “最小值最大化” 的问题。

一、适用场景与单调性

二分答案能起作用，前提是 答案具有单调性。什么意思呢？

• 如果问题要求“最大值最小”，那么随着猜测值变大，可行性会从“可行”逐渐变为“不可行”（或者反过来）。
• 如果问题要求“最小值最大”，那么随着猜测值变大，可行性会从“不可行”变为“可行”。

例子：
你要在一条直线上建 m 个仓库，每个仓库的服务半径尽量小（即“最大值最小化”）。如果猜服务半径是 r，那么可以检查能否用 m 个半径为 r 的仓库覆盖所有点。

• 如果 r 很小，可能覆盖不了，不可行。
• 如果 r 很大，肯定能覆盖，可行。
• 随着 r 增大，可行性从“不可行”变为“可行”，所以目标是找到 最小的可行 r。这就是单调性。

在写程序时，只要你发现一个问题的答案有一个“可行/不可行”的分界点，并且这个分界点随着答案是单调的，就可以用二分答案。

二、生活中的更多例子

分苹果：有 n 个苹果，重量各不相同。要把这些苹果分给 m 个同学，每个同学拿到的苹果总重量 尽量平均，但必须保证每个同学拿到的总重量 不小于某个最小值。问这个最小值最大能是多少？

• 猜一个最小值 k，检查能否把苹果分成 m 份（每份可以包含多个苹果），使得每份总重量都 ≥ k。
• 如果 k 太大，分不出来；k 合适就能分。我们要找最大的可行 k。

考试划分数线：学校要划一条录取分数线，让恰好 m 个学生被录取（或不超过 m 个）。假设每个学生有个分数，猜一个分数线 s，检查分数 ≥ s 的学生人数是否 ≤ m（或 ≥ m）。这也是二分答案的典型应用。

三、二分答案的三个关键步骤

1. 确定答案的范围

   • 左边界 left：题目中可能出现的最小值（比如 1、0 或某个下限）。
   • 右边界 right：题目中可能出现的最大值（比如所有物品的总和、最长木棍的长度等）。
   • 有时还需要根据题目调整边界（比如长度不能为 0）。

2. 编写可行性判断函数 can(x)

   • 输入一个猜测值 x，返回 True 或 False，表示 x 是否可行。
   • 这个函数是二分答案的核心，必须写对 —— 要仔细理解题目的“可行”标准。

3. 二分查找

   • 常见模板（求最大值时）：

while left <= right:
    mid = (left + right) // 2
    if can(mid):
        ans = mid          # 记录当前可行解
        left = mid + 1     # 尝试更大的值
    else:
        right = mid - 1    # 不可行，缩小范围

• 如果要求的是最小值，则判断逻辑相反：当 can(mid) 可行时，尝试更小的值（right = mid - 1），并记录答案。

四、Python 代码实现（经典切木棍）

下面是一个经典二分答案模板：在长度为 n 的木棍中，切出至少 m 根长度为 k 的小木棍，求 k 的最大可能值。

def can_cut(sticks, m, k):
    """检查能否切出至少m根长度为k的小木棍"""
    count = 0
    for s in sticks:
        count += s // k   # 每根木棍能切出几根
    return count >= m

def max_length(sticks, m):
    """二分查找最大可能的长度k"""
    left = 1                # 最小可能的长度
    right = max(sticks)     # 最大可能的长度（最长木棍）
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        if can_cut(sticks, m, mid):
            ans = mid          # mid可行，记录答案，尝试更大
            left = mid + 1
        else:
            right = mid - 1    # mid不可行，需要更小

    return ans

# 测试：3根木棍长度[10, 8, 5]，需要至少切出4根等长小木棍，求最长的小木棍长度
sticks = [10, 8, 5]
m = 4
result = max_length(sticks, m)
print(f"最长可以切出的长度是：{result}")   # 输出 5（因为k=5也可行，但原示例中如果m=6会输出3）

代码讲解：

1. 检查函数 can_cut：给定一个猜测的长度 k，计算所有木棍总共能切出多少根长度为 k 的小木棍（用 // 向下取整）。如果总数 >= m，说明 k 可行。
2. 二分主函数 max_length：设定搜索范围 [1, 最长木棍长度]。每次取中间值 mid，调用 can_cut 判断。
   • 如果可行，说明可以尝试更大的 k，所以记录 ans = mid，并 left = mid + 1。
   • 如果不可行，说明 k 太大，需要减小，所以 right = mid - 1。
3. 最终 ans 就是最大的可行长度。注意 while left <= right 保证全覆盖。

（注：上述示例中，若 m=4，实际最大长度为 5。若想得到 3，可将 m 改为 6，因为 10//3=3,8//3=2,5//3=1 共 6 根，k=4 时只有 5 根不够 6）

五、新手常见错误

六、另一个完整示例：分苹果

题目：有 n 个苹果，重量分别为 weights。要把这些苹果切成小块（每块必须整克），然后分给 m 个小朋友，每个小朋友拿到一小块（重量要相同）。问每个小朋友最多能拿到多少克苹果？（允许浪费）

思路：跟切木棍完全一样，只是把木棍长度换成了苹果重量。我们直接套用模板。

def can_divide(weights, m, gram):
    """检查能否切出至少m块重量为gram的苹果块"""
    total = 0
    for w in weights:
        total += w // gram   # 每个苹果能切出几块
    return total >= m

def max_gram(weights, m):
    """二分查找每个小朋友最多能获得多少克苹果"""
    left = 1                    # 至少1克
    right = max(weights)        # 最多不能超过最重的一个苹果
    best = 0

    while left <= right:
        mid = (left + right) // 2
        if can_divide(weights, m, mid):
            # mid可行，尝试更大
            best = mid
            left = mid + 1
        else:
            # mid不可行，减小
            right = mid - 1

    return best

# 测试：有3个苹果重量 [9, 7, 4]，分给3个小朋友
weights = [9, 7, 4]
m = 3
result = max_gram(weights, m)
print(f"每个小朋友最多可以拿到 {result} 克苹果")  # 输出 4

验证：

• 猜 4 克：9//4=2, 7//4=1, 4//4=1 → 共 4 块 ≥ 3，可行。
• 猜 5 克：9//5=1, 7//5=1, 4//5=0 → 共 2 块 < 3，不可行。
  因此最大值是 4。

七、相关知识点指引

• 二分查找：二分答案的本质是“二分查找”思想在答案空间上的应用。建议先掌握经典二分查找（在一个有序数组中找某个数）。
• 贪心算法：二分答案的验证函数常常结合贪心策略来写（比如先排序、再尽可能多地放置物品）。
• 前缀和与差分：某些验证函数需要快速计算一段区间的和，可以用前缀和优化。
• 高级二分答案：当答案范围很大时，还可以配合“二分答案 + 二分图匹配”等复杂验证。

举一反三练习：

1. 有 n 本书，每本书厚度不同。要把书分成 m 组连续的书，每组的总厚度尽量平均，求 每组总厚度的最大值最小 是多少？
2. 有 n 个学生排队，每个人的身高不同。要选出 m 个学生参加拔河，要求 选出的人中身高极差最小（最大值与最小值的差）。请问这个极差最小是多少？

学会了二分答案思想，你就能轻松解开很多看似很难的题目！下次遇到“最大/最小可行值”问题，记得先想一想：能不能猜一个答案，再写个函数验证它？