第一次在在线刷题平台上碰到“分巧克力”这道题时，我并没有太当回事。候选边长是整数、要切成同样大小的正方形、人数固定，看起来无非是从大到小试一遍。可真把代码交上去，才发现在边界、数据范围和二分写法上，隐藏了不少值得掰开揉碎讲清楚的东西。这篇文章以“进阶80题 分巧克力”为线索，把从题干解读到判定函数、从二分模板到提交踩坑的完整链路整理出来，给同样在刷二分答案专题的同学做个参考。

这道题的价值不在于它本身难，而在于它像一把钥匙：一旦你真的搞懂了它的单调性来源和二分边界设定，“二分答案”这一类题型也就基本拿下了。下面我按自己复盘时的顺序展开。

1. 题干拆解：正方形、整数边长、至少 K 块

1.1 原题到底问的是什么

各个平台的措辞略有差别，但核心模型非常统一：

有 N 块长方形巧克力，第 i 块的长是 H_i、宽是 W_i。现在要把这些巧克力切成若干个大小完全相同的正方形小块，正方形边长必须为正整数。现有 K 个小朋友，每个小朋友拿一块，所以切出来的正方形总数至少要有 K 块。问：正方形边长最大可以是多少。

输入通常是这样：

2 10 6 5 5 2

第一行是 N 和 K，后面 N 行是每块巧克力的 H_i、W_i，输出就是一个整数，表示最大可行边长。

这里有几个容易忽略的限定：

• 所有正方形边长必须相同，而不是每块巧克力各自切各自的最大方块。
• 边长是整数，不能出现 2.5 这种结果。
• 要求是“至少 K 块”，不是“恰好 K 块”。多余的正方形没人拿也没问题。
• 每块巧克力上切完剩下的边角料可以完全丢弃，不需要拼接到其他巧克力上。

这几点决定了我们不能用一个“看起来差不多”的经验公式去猜答案，而必须对每个候选边长进行精确校验。

1.2 为什么这题不是“切完再看”的贪心题

有人第一反应是：把总面积除以 K，再开根号，向上或向下取整不就行了吗？这个思路很直观，但立刻会被一个反例击穿。

假设有两块巧克力，分别是 1×9 和 1×9，K = 2。总面积为 18，平均每人 9 格，开根号正好是 3，看起来每块都能切出 3×3 的正方形。可实际上宽度只有 1，边长一旦超过 1，第一刀都切不下去。真实答案只能是 1。

问题就出在：切正方形不仅看面积，还要看长宽两个方向上分别能放几个。用面积反推边长，等于默认所有面积都可以完美重构为正方形，但这在矩形切割里不成立。

也有人想“从大到小枚举边长，找到第一个能满足 K 块的”，这个思路本身方向对，但效率不行。N 和边长的上限都是 100000 级别，最坏情况下枚举 10 万次边长、每次扫描 10 万块巧克力，运算量是 10^10 次，任何普通评测环境都扛不住。

1.3 数据范围决定了必须压缩枚举次数

正是这个数据范围，把这题从“暴力题”推到了“二分答案题”。题目允许我们承受的复杂度大约是几百万次运算，而二分查找刚好能把“从 1 到 100000 找答案”这个问题压缩成大约 17 次判断。每次判断扫描一遍 N 块巧克力，总运算量只有百万级，这就是二分答案在这道题里登场的原因。

2. 单调性曲线：二分搜索的地基

2.1 手算一张“边长—块数”表

二分答案不是玄学，它依赖一个非常硬的数学性质：可行性随边长单调变化。为了看清这一点，我拿一个具体例子手算过。

假设有 3 块巧克力，目标是至少切出 6 块：

3 6 10 10 5 8 3 4

当边长 S 取不同值时，每块巧克力能切出的整数块数为：(H_i / S) * (W_i / S)，其中除法是向下取整。算出来是这样一张表：

这张表最有信息量的一点是：满足和不满意的分界线非常清晰，边长从 1 到 4 都满足，从 5 开始就不满足。不存在“5 满足、4 不满足”这种来回跳的情况。

2.2 为什么可行性是连续区间

这种单调性的来源值得说透。

对第 i 块巧克力，它在边长 x 下能贡献的正方形数量是：

floor(H_i / x) * floor(W_i / x)

x 增大时，两个向下取整的结果只会保持不变或变小，不可能变大。因此每一块的贡献都是关于 x 的单调不增函数。

把 N 块巧克力加起来，总块数仍然是一个单调不增函数。

于是我们可以得到一个关键结论：如果边长 x 能切出至少 K 块，那么所有比 x 小的边长也一定能；反之，如果 x 切不出 K 块，那么所有比 x 大的边长也不可能切出来。

换句话说，可行边长在数轴上形成了一段连续区间：从 1 开始，一直到某个最大值，然后戛然而止。我们的任务就是找到这段连续区间的右端点。

2.3 合理设定上下界，别让二分跑偏

二分前要先确定搜索区间。下界很明确：1。因为题目保证糖果总数足以分给 K 个人，所以边长为 1 时，可以把每块巧克力都拆成 1×1 的小方格，总数一定不小于 K。

上界则有两种取法。最简单的是取所有巧克力长和宽里的较大值，比如记下最大 H 和最大 W，那么答案不可能超过 min(最大 H, 最大 W)，因为任何一边不够长，就切不出更大边长的方块。如果想更严谨一点，还可以取 max( min(H_i, W_i) )，也就是单块巧克力“最宽的短板”里最大的那个。

实际上二分搜索对右边界并不敏感，取一个偏大的右边界只会多花几次循环。真正需要小心的是下界，后面第 4 节会专门讲为什么有些人会把下界写成 0，然后踩到除零错误。

3. 判定函数与二分模板：把思路变成代码

3.1 判定函数：每一块能贡献多少

二分答案里的每次判断，通常被封装成一个 check(x) 函数，输入候选边长 x，输出 True 或 False。

这道题的 check 函数特别简单：

for 每一块巧克力: cnt += (H_i / x) * (W_i / x) // 整数除法 if cnt >= K: return true return false

不要小看这个函数。它把“这块巧克力能在长方向放几个、在宽方向放几个”变成了两个整数除法。10×10 的巧克力在边长为 4 时，长方向 10/4 = 2，宽方向 10/4 = 2，所以贡献 4 块；5×8 的巧克力在边长为 4 时，长方向 5/4 = 1，宽方向 8/4 = 2，所以贡献 2 块。整个过程不涉及任何贪心选择，也不需要考虑巧克力之间的搭配，因为每块的贡献彼此独立。

3.2 二分循环怎么写才不容易错

二分写法五花八门，我强烈建议初学者直接背一种最不容易出错的模板：维护答案候选变量的左闭右闭二分。

思路是：

• left = 1，right = 设定的上限，ans = 0。
• 只要 left <= right，就取 mid = left + (right - left) / 2。
• 如果 check(mid) 为真，说明 mid 可行，记录 ans = mid，然后去右半边找更大的答案，即 left = mid + 1。
• 如果 check(mid) 为假，说明 mid 太大，去左半边找，即 right = mid - 1。
• 循环结束后输出 ans。

这个模板把“当前找到的最大可行答案”显式保存下来，即使区间不断缩小，答案也不会丢失。

3.3 C++ 可提交版本

我做题时通常用 C++，完整代码如下：

#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; bool check(vector<int>& h, vector<int>& w, int n, int k, int x) { ll cnt = 0; for (int i = 0; i < n; ++i) { cnt += (ll)(h[i] / x) * (w[i] / x); if (cnt >= k) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> h(n), w(n); int maxH = 0, maxW = 0; for (int i = 0; i < n; ++i) { cin >> h[i] >> w[i]; maxH = max(maxH, h[i]); maxW = max(maxW, w[i]); } int left = 1; int right = min(maxH, maxW); int ans = 1; while (left <= right) { int mid = left + (right - left) / 2; if (check(h, w, n, k, mid)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } cout << ans << "\n"; return 0; }

代码里有一处必须注意：(ll)(h[i] / x) * (w[i] / x)这里把第一个因子转成了 long long，否则两个 int 相乘时可能溢出。这一点在第 4 节会专门展开。

3.4 Python 可提交版本

如果你习惯用 Python，代码会更短，不过原理完全一致：

n, k = map(int, input().split()) chocolates = [tuple(map(int, input().split())) for _ in range(n)] def check(length): total = 0 for h, w in chocolates: total += (h // length) * (w // length) if total >= k: return True return False max_h = max(h for h, _ in chocolates) max_w = max(w for _, w in chocolates) left, right, ans = 1, min(max_h, max_w), 1 while left <= right: mid = (left + right) // 2 if check(mid): ans = mid left = mid + 1 else: right = mid - 1 print(ans)

Python 里整数不会溢出，写起来更省心。但要注意，如果输入规模特别大，多次调用 check 时 Python 的循环开销会偏高。好在二分的判断次数只有大约 log2(100000) ≈ 17 次，每次扫描 N 个元素，百万级运算对 Python 来说也完全够用。

3.5 时间复杂度与样例验证

整个算法的时间复杂度是 O(N log V)，其中 V 是搜索区间长度。log2(100000) 大约 17，所以实际运算量只有 17N 次左右，相比暴力枚举的 N·V，压缩幅度非常可观。

拿上一节的三块巧克力例子跑一遍，答案会稳定输出 4，和第 2 节的表格一致。看到这个结果的时候，二分答案的合理性才算真正落到了实处。

4. 我提交时踩过的坑：这部分比模板更值钱

模板谁都会抄，真正拉开差距的是调试和边界处理。下面几个错误，我至少各踩过一次。

4.1 中间结果溢出：int 的 10^10 陷阱

第一版代码我写的是：

cnt += (h[i] / x) * (w[i] / x);

看起来天经地义，但一旦 h[i] 和 w[i] 都接近 100000，x 又比较小，比如 x = 1，那么(h[i] / x) * (w[i] / x)就是 10^5 × 10^5 = 10^10。这个数字远超出 32 位 int 的范围，溢出后 cnt 会变成负数，检查结果完全乱套。

解决办法有两个方向：一是把中间乘积转成 long long，我在上面代码里就是这么处理的；二是在cnt >= K条件满足后立刻返回 True，既防止溢出扩散，又能减少后续不必要的计算。这两种优化我都建议加进去。

4.2 二分下界写成 0：除零错误就在眼前

另一个经典错误是把 left 初始化为 0。逻辑上看，0 确实比任何正数都小，放在二分区间里似乎无害。可一旦 left 是 0、right 是 1，那么mid = (0 + 1) / 2 = 0，check(0) 里会直接出现除零错误。

所以下界必须从 1 开始，或者单独处理 x = 0 的情况。边长是正整数，这是题目明确给的限定，完全没必要把这个非法值放进来。

4.3 “至少 K 块”不等于“必须多于 K 块”

判定条件要写成cnt >= K，而不是cnt > K。这个坑特别隐蔽，因为绝大多数样例里的可行答案都会明显大于 K，少一两个块看不出问题。可一旦遇到边界数据，比如刚好正好切出 K 块时，把>写错的人就会少算一个合法答案，直接导致 Wrong Answer。

我后来给自己定了一个习惯：所有涉及“至少”“不少于”的判定，都先默写>=，再对照题意检查一遍。

4.4 提交前必跑的四组自测用例

与其等评测机告诉你错了，不如本地先跑几个边界用例：

我一般在交题前把这些用例测一遍，能过滤掉九成低级错误。尤其是第二组“极窄巧克力”，专门用来验证判定函数对短边的处理是否正确。

5. 把“二分答案”装进脑子里

分巧克力做完之后，我意识到它的解题套路可以提炼成更一般的模型，之后的很多题都受益于这次复盘。

5.1 同一种模式的其他题目

和“分巧克力”几乎同构的题目不少，最常见的就是切割木棒问题：给定若干根长度不等的木棒，要切割成若干根长度相同的小棒，且数量不少于 M，求单根小棒的最大长度。

这类题的判定函数都是同一个形状：给定候选长度 x，计算sum(H_i / x)或sum((H_i / x) * (W_i / x))，然后和阈值比较。区别只是从一维除法变成了二维两个除法的乘积。

另一种常见变体是“分发饼干”类问题，判定时要把每块饼干尝试分配给小孩，逻辑复杂一点，但整体思路仍是二分答案：候选答案满足单调性，check 函数负责验证某个中间值是否可行。

5.2 快速判断一个题能不能用二分答案

我现在拿到一个新题，会先问自己三个问题：

第一，答案是否存在一个明确的有序区间？比如 1 到某个上限，或者最小值到最大值。

第二，给定一个候选答案，能否在可接受的时间内验证可行性？验证过程通常是一个扫描或一次排序。

第三，可行性是否随答案单调变化？这是最关键的一条。可以从小规模数据手算，看可行区间是否连续，而不是在某个点反复横跳。

如果三个问题的回答都是肯定的，那这题大概率就是二分答案，剩下的事情就是写好 check 函数、选对边界、提交前跑一遍自测。

5.3 我的最终模板总结

最后留一份我存在代码片段里的二分答案模板：

def feasible(x): # 根据题目实现判定逻辑 pass left, right = lower_bound, upper_bound best = None while left <= right: mid = (left + right) // 2 if feasible(mid): best = mid # mid 可行，先记录再找更大的 left = mid + 1 else: right = mid - 1 # mid 不可行，只能在更小区间找 print(best)

这套模板配合“单独封装判定函数”的习惯，几乎能覆盖所有求最大可行答案的二分题。遇到求最小可行答案的题，只需把if feasible(mid):分支里的left = mid + 1和right = mid - 1对调，再加一个判断即可。

“分巧克力”这道题我已经刷过不止一次，每次做都会发现新的细节。它真正教会我的，不是背一个二分模板，而是理解单调性从哪来、边界该怎么定、整数溢出会在哪里咬人。把这些经验迁移到下一道二分题时，你会发现自己已经从“抄模板”进步到了“设计解法”的阶段。以后刷进阶题单再遇到类似题，不妨先问一句：候选答案的可行性是不是单调的？如果是，二分就已经赢了一半。