蓝桥杯“分巧克力”是很多人在算法入门阶段第一次认真接触“二分答案”的经典题目。题面很生活化你有 N 块长宽已知的矩形巧克力要切出 K 块同样大小的正方形分给小朋友问正方形的最大边长能到多少。乍一看像小学奥数可真上手写代码卡人的地方根本不在“怎么切”而在“怎么快速判断某个边长行不行”以及“怎么高效逼近正确答案”。下面我从一个刷题者的视角把这道题的暴力思路、二分原理、三种语言实现、常见坑位都拆开过一遍。无论你是刚开始备战蓝桥杯的 C/C 选手还是用 Java、Python 报名参赛都能直接拿去参考。看完不光能 AC 这一题还能把“二分答案”这套通用解法迁移到切绳子、木材加工、跳石头等同类题目上。1. 读懂题目分巧克力的真正难点1.1 题目到底在说什么先把题面翻译成自己的话第一行给两个整数 N 和 KN 是巧克力块数K 是小朋友个数。接下来 N 行每行两个整数 Hi、Wi表示每块巧克力的长和宽。所有巧克力都是矩形切的时候必须沿着边平行地切目标是分出 K 块大小完全一样的正方形问正方形的边长最大能取多少。这里面有几个隐藏条件容易被忽略第一正方形的边长必须是整数原题要求输出整数答案所以不需要处理小数第二每块巧克力可以切成多个正方形也可以剩下边角料但边角料只能扔掉不能把两块巧克力的碎块拼成一个正方形第三题目保证在边长至少为 1 的方案下一定有解也就是说最坏情况可以把每块巧克力都切成 1×1 的小方块来凑数。数据范围也决定了这道题的玩法N、K 都能到 100000Hi、Wi 也都能到 100000。这个规模直接把很多“看起来正确”的枚举思路判了死刑逼着你去找更高效的办法。1.2 暴力思路为什么会超时最容易想到的思路是从大到小枚举边长 x每枚举一个 x 就把所有巧克力扫一遍统计总共能切出多少块正方形一旦总块数大于等于 K就把当前 x 输出并结束。这个思路逻辑上完全正确平时在本地跑小样例也看不出问题一提交就超时。算一下复杂度就清楚了边长的合法范围从 1 到 100000最多要枚举 100000 种可能每次枚举都要遍历 N 块巧克力N 也是 100000乘起来就是 10 亿次操作。如果每个操作再有点开销十亿这个量级在竞赛环境下基本是必挂的。更直观点说就算机器每秒能跑一亿次基础运算十亿次操作也要奔着十秒去而题目通常只给你一两秒。所以分巧克力这道题的核心教育意义就在这里同样的“枚举所有答案”目标换一个更有组织的搜索方式复杂度能从 O(N × M) 直接降到 O(N log M)这就是二分的力量。1.3 核心转化公式一块巧克力能切出多少个在写任何算法之前得先把“怎么计算一块巧克力能切出几个边长为 x 的正方形”这一步彻底搞清楚。公式非常直观对于一块 Hi × Wi 的巧克力长方向能容纳 Hi / x 个正方形向下取整宽方向能容纳 Wi / x 个相乘就是这一块能贡献的数量。写成代码就是cnt (Hi / x) * (Wi / x)这里的除号在 C、Java 和 Python 里都是整除语义前提是变量全是正整数。这个公式看起来简单但有一个特别容易想歪的点为什么不能用面积直接除比如用总面积 Hi × Wi 除以 x 的平方这样算出来的结果会偏大因为面积法假设碎料可以任意拼接但实际题目不允许。举一个生活化例子一块 5×5 的巧克力要切 3×3 的正方形面积法会告诉你 25÷9≈2.7仿佛能切两块实际上只能切一块一行放不下两个 3这一块巧克力的剩余空间全是边角料。理解了这条后面写 check 函数时就再也不会在公式上翻车。2. 二分答案为什么这是标准解法2.1 单调性是二分成立的前提二分不是随便找个中间值碰运气它成立的数学基础是可行性关于边长具有单调性边长 x 越小每块巧克力能切出的块数就越多总块数只可能增加或者不变边长 x 越大总块数只可能减少或者不变。因此一定存在一个分界点 ans使得所有 x ≤ ans 都可行所有 x ans 都不可行。这个性质极其重要。它意味着如果我们把所有可能的边长从 1 到最大边长排成一排那么这一排开关的状态一定是前面一串 true、后面一串 false中间最多只切换一次。正因为状态是单调排列的才能用二分法快速定位这个分界点。这也是所有“二分答案”题目的共同特征可行性与答案之间满足单调关系而不是乱七八糟的随机分布。有的同学会把单调性和 check 函数混为一谈。记住一个简单区分单调性是题目的数学性质是由题目条件天然决定的check 函数是我们为了验证某个候选值是否可行而写出来的工具。两个都要有缺一不可。2.2 判定函数 check 的写法与理解二分的外层框架很简单核心工作其实全部集中在 check 函数里。check(x) 要做的事是遍历所有巧克力把每块能切出的正方形块数累加起来最后判断总数是否大于等于 K。如果大于等于 K返回 true说明边长 x 是可行的我们可以尝试更大的值否则返回 false说明边长 x 太大需要往小里找。这里有一个非常实用的小优化统计 cnt 的过程中一旦 cnt 已经达到 K立刻 return true不需要继续处理后面的巧克力。因为 check 只需要回答“行不行”并不需要回答“到底能切出多少块”。这个提前剪枝在数据极端的时候能省下大量时间比如某块巧克力特别大第一块切完就已经满足 K那后面九万九千九百九十九块都不用看了。check 函数的复杂度是 O(N)。外层二分每次把搜索区间砍半整体复杂度 O(N log M)其中 M 是答案上界。代入 N100000、M100000 算一下log₂100000 大约是 17全部操作量大约在 170 万左右这个量级对任何语言来说都是轻松无压力的。2.3 边界与死循环为什么 mid 要加 1分巧克力最主流的二分写法长这样while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }很多初学者会把上面代码里的 mid 写成(l r) 1结果在某些数据下直接死循环。用一组具体数字解释就明白了假设当前 l4、r5并且 check(4) 为 true、check(5) 为 false。如果用mid (l r) 1mid 等于 4check(4) 为 true于是 l 被更新成 4区间 [4, 5] 完全没有变下一次循环还是同样的情况程序卡死。换成mid (l r 1) 1之后同样在 l4、r5 时mid 等于 5check(5) 为 false于是 r 被更新成 4区间收敛到 [4,4]循环结束正确输出 4。所以这条经验值得背下来当 check 为真的分支是l mid时mid 必须取上中位数也就是(l r 1) / 2。另一种常见写法是取左中位数但更新规则变成while (l r) { int mid (l r) 1; if (check(mid)) l mid 1; else r mid; } cout l - 1;这种写法里 l 最终指向第一个不可行的值真正的答案是 l-1。两种写法本质等价但千万别混着用左边取中位数的习惯配右边更新规则或者反过来都会出问题。3. 参考代码与关键细节三种语言的实现3.1 C 参考实现#include bits/stdc.h using namespace std; const int MAXN 100005; int n, k; int h[MAXN], w[MAXN]; bool check(int x) { long long cnt 0; for (int i 0; i n; i) { cnt (long long)(h[i] / x) * (w[i] / x); if (cnt k) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; int maxLen 0; for (int i 0; i n; i) { cin h[i] w[i]; maxLen max(maxLen, min(h[i], w[i])); } int l 1, r maxLen; while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; } cout l \n; return 0; }代码里有几个细节值得展开。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是给 cin 提速用的。标准输入输出流默认会和 C 的 stdio 保持同步导致 cin 读入偏慢大输入下可能拖后腿。在竞赛代码里取消同步是基本操作能明显减少 IO 耗时。cnt使用 long long 是必须的原因后面还会强调。看这句cnt (long long)(h[i] / x) * (w[i] / x)如果 h 和 w 都等于 100000、x 等于 1那么单块巧克力贡献就是 100000 × 100000 10000000000也就是一百亿远超 int 的二十亿上限。如果不在乘法前把其中一个因子强转 long long整个乘法会先按 int 计算然后溢出结果变成负数check 直接乱套。右边界初始化成max(min(h[i], w[i]))也就是所有巧克力短边中的最大值。这个上界是紧的如果边长超过了某一块巧克力的短边这一块就一个正方形都切不出来全局最大可行边长自然不可能超过所有短边中的最大值。也可以直接固定r 100000因为题面给了这个范围二分也就多跑几次循环不影响正确性但用 maxLen 写出来语义更清晰也能少两轮迭代。3.2 Java 参考实现import java.util.*; public class Main { static int n, k; static int[] h new int[100005]; static int[] w new int[100005]; static boolean check(int x) { long cnt 0; for (int i 0; i n; i) { cnt (long)(h[i] / x) * (w[i] / x); if (cnt k) return true; } return false; } public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); k sc.nextInt(); int maxLen 0; for (int i 0; i n; i) { h[i] sc.nextInt(); w[i] sc.nextInt(); maxLen Math.max(maxLen, Math.min(h[i], w[i])); } int l 1, r maxLen; while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; } System.out.println(l); } }Java 版本里最容易犯错的就是这行cnt (long)(h[i] / x) * (w[i] / x)。如果写成(long)((h[i] / x) * (w[i] / x))那么乘法已经按 int 计算完并且溢出了再转 long 也救不回来。必须先转换其中一个因子强制整个乘法以 long 精度执行。(l r 1) 1里的是无符号右移等价于整除 2而且因为 Java 的 int 左移后符号位问题不用考虑——这里 l、r 全是正数其实用(l r 1) / 2也完全一样只是纯粹的习惯写法。Scanner 在 10 万行的输入规模下通常足够快但如果担心输入成为瓶颈可以换BufferedReader对整体算法影响不大。3.3 Python 参考实现import sys def main(): it iter(sys.stdin.buffer.read().split()) n int(next(it)) k int(next(it)) chocolates [] max_len 0 for _ in range(n): hi int(next(it)) wi int(next(it)) chocolates.append((hi, wi)) max_len max(max_len, min(hi, wi)) def check(x): cnt 0 for hi, wi in chocolates: cnt (hi // x) * (wi // x) if cnt k: return True return False l, r 1, max_len while l r: mid (l r 1) // 2 if check(mid): l mid else: r mid - 1 print(l) if __name__ __main__: main()Python 没有整数溢出问题所以 check 里的 cnt 不用担心类型这也是 Python 选手的一个优势。读入采用sys.stdin.buffer.read().split()一次性读取全部字节再分割比一行行input().split()要快不少。虽然 10 万行数据用普通 input 也不至于超时但在竞赛里能省一点是一点。hi // x是 Python 的整除写法和 C、Java 里正整数的/行为完全一致。check 里的提前返回同样安全只要 cnt 达到 k 就立刻结束循环因为此时已经可以判定边长 x 可行。提交时如果平台支持 PyPy优先选 PyPy跑这种循环密集的题目通常比 CPython 快一个档次。3.4 为什么要特别强调右边界我见过很多人把r直接写成 100000问我行不行。答案是行因为题面保证了边长上限就是 100000这么做不会结果错误只会多几次二分迭代。但用max_len更严谨因为它的推导依赖题目本身任何可行边长的上界都不可能超过所有巧克力短边中的最大值。无论你选哪种只需保证l的初值至少是 1并且全程序不要出现除以 0 的情况。还有一个小问题如果输入规模很小比如只有一块巧克力认真模拟一下就会发现这个程序从输入到输出都非常干净。我曾经用一块 100000×100000、K1 的极端数据去测试答案应该是 100000代码能正确输出说明右边界初始化没有把正确答案排斥在外。4. 高频坑位与排查建议4.1 死循环到底怎么排查死循环是二分题最让人头疼的问题因为它不报错只是卡住不输出。排查手段很简单在 while 循环里临时加一行打印输出当前的 l、r、mid 以及 check(mid) 的结果眼看它卡在哪一组数据上。如果发现某次迭代里l更新之后没有变小、r更新之后没有变大那就是更新规则和 mid 取法不匹配。之前说过当 check 为真时执行l mid此时 mid 必须取上中位数。如果还记不住可以用一个更保守的心法永远保证“每次循环区间长度必须严格缩短”。只要l r那么r mid - 1一定小于 rl mid一定大于 l两个分支都能让区间变小。反过来如果 mid 取的是左中位数而这个值正好等于 ll mid之后区间长度不变自然死循环。4.2 特殊用例与手算验证二分答案类题目最怕边界上的答案算错分巧克力有一个特别适合手算的用例N1、K100000、巧克力尺寸是 100000×100000。只有一块巧克力要切出 10 万块正方形。边长取 316 时100000 整除 316 等于 316能切出 316×31699856 块不够 10 万边长取 315 时100000 整除 315 等于 317能切出 317×317100489 块够了。所以正确答案是 315。这个用例能一次性验证二分模板、边界条件和 check 是否正确。如果代码输出 316 或者其他奇怪的值一定能从 check 函数里找到问题。平时准备竞赛时给每道题准备几个这种“极端小数据”是很划算的习惯成本低收益高。4.3 类型溢出和数据范围陷阱类型溢出是 C 和 Java 选手最常踩的坑。刚才算过单块巧克力在一组极端输入下贡献的值能达到 100 亿int 根本装不下。C 里如果cnt声明成 int累加过程中就可能溢出成负数check 返回值跟着错乱最终答案看起来毫无规律。更隐蔽的是 Java 版本因为 Java 的整数乘法是左结合(h[i] / x) * (w[i] / x)会先按 int 乘结果溢出以后才赋给 long。很多同学明明看到 cnt 是 long 类型却忽略了中间的乘法已经提前溢出。正确的做法是显式转换其中一个因子让整个乘法在 long 的空间里完成。4.4 常见错误速查表错误现象根本原因解决办法程序卡住不输出mid 取下中位数且 lmid 导致区间不变改用(l r 1) 1答案比正确值小 1二分模板混用l 最终指向不可行值统一使用一套更新规则输出负数或异常大cnt 类型溢出C 用 long longJava 显式转 long大样例超时cin 未关闭同步 / Python 用逐行读取加 ios::sync_with_stdio(false)Python 用 buffer.read边界答案错误右边界初始化太小排除了正确答案r 至少取最大短边或直接用题目给的上限4.5 二分左右初始值的选择l 初始化为 1而不是 0。原因很简单第一题目保证一定有解第二check(0) 会导致除以 0运行时直接崩溃或报错。如果你为了安全把 l 设成 0就必须在 check 里对 x0 做特殊处理完全没有必要。真正需要动脑筋的是 r 的取值。分巧克力里 r 可以取所有巧克力短边的最大值也可以取题面上限 100000。如果题目改一下Hi、Wi 能到 10⁹那固定 100000 就不适用了所以更通用的做法是动态计算 r。这也符合二分答案的标准套路先确定答案的上下界再在上下界之间二分。5. 从分巧克力到一类题二分答案的识别与迁移5.1 哪些题目适合二分答案刷题量上来之后你会遇到很多和分巧克力长得不一样的题但解法都是二分。它们的共同特征可以总结成几条题目问的是“最大值最小”或“最小值最大”或者干脆问“最大能到多少”“至少需要多少”。答案落在一个有限的区间里这个区间可以是整数区间也可以是实数区间。存在一个 check 函数能快速判断某个候选答案是否可行。可行性随答案的变化是单调的即答案越小越容易满足或者越大越容易满足。直接暴力枚举会超时。比如切绳子问题给你几段绳子要切成 m 段等长问最大长度是多少。这个题的 check 就是把每段绳子长度除以候选长度再累加判断是否大于等于 m。它的数学结构和分巧克力几乎一像素不差只是从二维矩形变成了一维线段代码甚至更短。跳石头问题也很有代表性要移走若干块石头使得最短跳跃距离尽量大。这里的 check 需要用贪心模拟跳石头的过程统计最少需要移走多少块才能让所有相邻跳跃距离都不小于候选值然后判断移走的数量是否超过限制。外层同样是二分区别只在 check 内部的实现逻辑。5.2 二分模板的通用写法对整数二分我自己习惯长期使用同一套模板避免在不同题之间摇摆while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }所有“找最大可行值”的整数题我都直接套这个模板只换 check 函数的实现。如果遇到“找最小可行值”的题模板会变成while (l r) { int mid (l r) 1; if (check(mid)) r mid; else l mid 1; }两套模板的核心原则是一致的每次循环必须把区间缩小怎么缩由 check 结果和题意决定。建议新手先死记一套另一套明白原理后自然就会写不要在一道题里反复切换模板那样特别容易把自己绕晕。5.3 浮点数二分的一点补充分巧克力是整数二分但很多同类题会要求输出浮点数比如切绳子求最大长度要保留两位小数。浮点二分有两种常见写法。一种是控制精度比如while (r - l 1e-5)另一种是固定循环次数比如做 100 次二分再输出。我更推荐固定次数法因为它不受问题精度设置影响也不会因为精度设得太大或太小而出问题。for (int i 0; i 100; i) { double mid (l r) / 2; if (check(mid)) l mid; else r mid; } printf(%.2f\n, l);浮点在更新时不用纠结中位数取上还是取下的问题因为 double 不存在整除导致的死循环。100 次循环已经把区间长度缩小到原来的 2 的一百次方分之一远超过 double 的有效精度足够任何比赛用了。最后分享一点个人体会。我备考时习惯把模板题整理成“套路卡片”分巧克力就是第一张题目特征是“求最大可行值”check 函数负责验证某个边长能不能切出足够数量的正方形二分模板固定套用边界初始化用短边最大值。之后遇到切绳子、木材加工、跳石头基本可以做到十分钟内完成迁移。每次写完二分题我还会手动构造两个极端用例丢进本地测一遍一个测最小答案一个测最大答案确认边界没问题再提交。这个习惯帮我挡住了很多次无谓的罚时希望也能帮到你。