东华OJ进阶系列第80题“分巧克力”是我刷题过程中印象很深的一道。题目不算长但把“二分答案”这个思想表现得特别典型——很多第一次做到它的人读完题第一反应是枚举边长然后发现时间爆炸最后才意识到真正的解法藏在对答案的二分上。每年带新人刷题的时候这道题我都会专门拿出来讲一遍因为它的坑很集中check函数怎么写、边界怎么取、数据范围要不要开大全都值得掰开揉碎聊一聊。这篇文章就围绕这道题把从读题到AC的完整链路拆给你适合正在OJ上刷题入门二分答案的同学也适合会写二分但总败在边界上的老手。1. 先别急着敲代码——把题目的限制条件吃透1.1 这道题到底在问什么“分巧克力”的题面常见版本是这样有N块巧克力第i块是Hi×Wi的长方形要切出形状相同、边长是整数的正方形分给K个小朋友每人一块求正方形的最大边长。这句话看着简单但信息密度不低。拆开看至少有三个硬性约束第一切出来必须是正方形不能是长方形第二边长必须是整数第三所有正方形大小相同。第三个条件尤其关键它意味着你不能给一个小朋友切大的、给另一个小朋友切小的所有人拿到的一定是同一尺寸。这里容易被忽略的是“每人一块”这四个字。题目要求的是切出K块正方形不是切出若干块然后分配更不是把一块大巧克力切成K份。换句话说只要你能在N块原始巧克力上切出至少K个相同大小的正方形这些正方形就可以视为已经分给K个小朋友了。至于是不是刚好K块、有没有剩余无所谓。这一点是后面check函数里判断条件用 K而不是 K的根本原因。另外注意每块巧克力切的时候是独立的。你不能把两块巧克力拼在一起再切也不能把一块巧克力切碎了重新组合成正方形。每块巧克力都是一个独立的矩形能切出多少块目标正方形取决于这个矩形自身的宽度和高度。这个约束直接决定了check函数的写法后面我会专门展开。1.2 数据范围决定算法方向很多初学者看到这种题第一反应是枚举边长从1开始试试到某个值发现不够K块了答案就是前一个值。这个思路本身没错但它对不对完全取决于数据范围。按常见版本的数据范围来讨论N和K一般在10^5级别巧克力的长宽也在10^5级别。如果枚举边长最坏情况下边长从1枚举到10^5每次都要扫描N块巧克力计算可切块数总复杂度就是10^5×10^5 10^10。这个量级在绝大多数OJ上都是跑不动的一两秒的时间限制下几乎是必超时。当然实测时如果数据水有些暴力写法可能也能苟过去但刷题不能靠赌数据得靠算法。数据范围还有一个隐藏的含义答案可能很大。边长最大值不会超过所有巧克力中较短边的最长值但即便只有10^5级别也足够说明所有计算结果都应该考虑用更大的类型来承载。这一点我在第4部分会专门说这里先有个印象。1.3 输出和判定的隐藏逻辑题目要你输出一个整数这个整数是“能分出K块的前提下正方形的最大边长”。这句话反过来读就是边长为x时如果能切出的总块数 ≥ K那x就是可行解如果 K那x就太大了。所以判定一个边长是否合法本质上就是在算“所有巧克力在边长为x时能切出的正方形总数”。这个判定过程本身是有规律的边长x越大每块巧克力能切出的块数就越少总数当然也越少。反过来x越小总数就越多。这个“越大越少、越小越多”的性质就是单调性。而这恰恰是二分答案能应用的前提。换句话说这道题表面上是几何题实际上你只需要关心一个单调变化的函数——边长到块数的映射剩下的就是在函数上找一个最大可行点。2. 从暴力枚举到二分答案——思路推导全记录2.1 暴力思路为什么走不通我刚开始刷到这题的时候第一版代码也是暴力的。代码长这样int ans 1; for (int x 1; x maxLen; x) { long long cnt 0; for (int i 1; i n; i) { cnt (h[i] / x) * (w[i] / x); } if (cnt k) ans x; else break; }这个写法逻辑完全正确但跑起来非常酸爽。如果所有数据都是10^5级别的满值这个循环差不多要执行10^10次。我当时在本地测了一组满数据跑了大概二十多秒。这要是在OJ上提交基本就是tle警告。暴力算法的思路价值在于帮你发现规律你从大往小枚举的时候cnt是逐渐增大的而且存在一个临界点过了这个点cnt就再也达不到K了。这个临界点就是我们要的答案。提到“从大往小枚举”我顺便说一句很多人喜欢从1往上枚举找到一个不满足的就退出这其实浪费了信息。如果你从大到小枚举第一个满足条件的边长就是答案直接return反而逻辑上更贴合“求最大值”的直觉。但不管从哪个方向枚举暴力复杂度都是一样的都需要进一步优化。2.2 单调性是二分的底气假设我们定义一个函数f(x)表示边长为x时能切出的正方形总块数。那么f(x)有一个非常明显的性质x增大时f(x)的值不会增大。这不是感性认识而是数学上可以严格保证的——每块巧克力的长宽都固定边长x增大h[i]/x和w[i]/x的结果要么不变要么变小乘起来自然不会变大。这个单调性意味着什么意味着f(x) K这个命题在数轴上是一个连续区间。左边全是true右边全是false或者反过来看你怎么定义。我们的目标是找到这个区间的最右端。二分查找的本质就是在有序数组里找一个值而这里f(x)虽然不是一个显式的数组但它的单调性让“按值域查找”成为可能。这就是二分答案和普通二分的区别普通二分查找是在数组下标上搜索目标值二分答案是在答案的值域上搜索可行解而判断一个值是否可行就用check函数。用生活里的场景来类比想象你有10个不同重量的西瓜想知道一个秤最多能称多少斤还能继续读数。如果秤的读数范围是0到100斤你不需要从1斤一次一次往上加而是先称50斤能读就加到75斤不能读就减到25斤每次排除一半。这里“能不能读数”就是check函数“最大值”就是答案。2.3 二分答案的框架有了单调性二分框架就顺理成章了。我们需要在答案的可能范围[1, maxLen]内二分。每次取中点mid调用check(mid)判断边长为mid时能否切出至少K块。如果能说明mid是一个可行解答案应该更大因此把左边界移动到mid1如果不能说明mid太大把右边界移动到mid-1。直到左右边界交错最后一个可行解就是答案。这个框架适用于所有二分答案题核心区别只在check函数的具体实现。对于分巧克力来说check函数就是遍历所有巧克力把每块能切出的块数累加起来判断是否大于等于K。整体复杂度是O(N * log(maxLen))log(10^5)大约17再乘以10^5的N总共不到200万次操作跟暴力的10^10完全不在一个数量级。3. 完整代码实现与逐段拆解3.1 一份可以直接提交的C代码下面是我在实际刷题中用的版本加了注释方便对着看#include bits/stdc.h using namespace std; const int MAXN 100005; int n, k; int h[MAXN], w[MAXN]; // check函数判断边长为x时能否切出至少k块正方形 long long 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 cnt; // 提前退出省一点时间 } return cnt; } int main() { scanf(%d%d, n, k); int maxLen 0; for (int i 0; i n; i) { scanf(%d%d, h[i], w[i]); maxLen max(maxLen, max(h[i], w[i])); } int l 1, r maxLen, ans 1; while (l r) { int mid (l r) / 2; if (check(mid) k) { ans mid; l mid 1; // mid可行尝试更大的边长 } else { r mid - 1; // mid太大缩小范围 } } printf(%d\n, ans); return 0; }这个代码在逻辑上非常直接。maxLen取所有巧克力长宽的最大值是因为边长不可能超过任何一块巧克力的横向或纵向尺寸。l从1开始因为边长至少为1才有意义。ans用来记录最后一个可行解这是避免边界混乱的小技巧。有人可能会问maxLen为什么取所有max(h[i], w[i])的最大值而不是所有min(h[i], w[i])的最大值答案是取所有max(h[i], w[i])的最大值更安全且一定不会漏掉可行解。因为如果某块巧克力的两边都小于x它确实切不出正方形但如果取所有边的最大值能保证不会出现“理论上应该有解但右边界设小了”的情况。取min的最大值在某些情况下会更紧但写起来要多个循环而且对二分复杂度没有质的改善所以通常就直接取所有边最大值了。3.2 check函数为什么是长宽分别除以边长再相乘这是这道题最核心、最容易写错的地方。正确的写法是(h[i] / x) * (w[i] / x)注意是整除不是面积相除。很多初学者会误写成(h[i] * w[i]) / (x * x)也就是用总面积除以正方形面积。这个写法在数学上看起来“差不多”但在实际切巧克力时是完全错误的。原因在于一块巧克力不能重新拼装。3×5的矩形要切出边长2的正方形总面积15正方形面积415除以4等于3按面积法答案是3块。但实际上3×5的矩形横着只能排1个2竖着只能排2个2最多切出2块。剩下一个1×5的细条和一个3×1的细条根本拼不出正方形。所以check函数的本质是几何计数横方向上能排下的个数是w[i] / x竖方向上能排下的个数是h[i] / x两者相乘才是这块矩形真能贡献的正方形数量。这跟实际铺地板是一个道理——你不能把边角料拿来拼凑每块正方形必须是完整地从矩形里切出来的。这个区别在数据小的时候暴露不出来样例可能轻松通过但遇到大矩形或者特定长宽比时面积法就会给出错误答案。这也是这类题喜欢埋的坑之一。3.3 两种二分模板的对比我在代码里用的是l r加ans记录的方式。还有一种常见写法是l r配合上取整int l 1, r maxLen; while (l r) { int mid (l r 1) / 2; // 注意这里1 if (check(mid) k) { l mid; } else { r mid - 1; } } printf(%d\n, l);这个模板的核心在于mid (l r 1) / 2为什么要加1因为如果不加当l mid时如果mid计算出来等于l就会陷入死循环。比如l 3, r 4mid (3 4) / 2 3如果check(3)成立执行l mid后l还是3r还是4无限循环。加上1之后mid (3 4 1) / 2 4就可以正常推进。两个模板没有高下之分我个人的体验是第一种l r ans适合新手逻辑直白不怕死循环ans变量帮你兜底第二种l r更简洁但上取整和边界条件需要理解透彻才敢用。如果你在比赛里写第二种模板建议在草稿纸上把l3, r4这种临界情况手动推一遍确认不会卡死再提交。4. 实战中的常见问题与避坑记录4.1 类型溢出最隐蔽的WA来源我在第1.2节提到数据范围是10^5级别但很多人写代码的时候就是忍不住用int。这里有一个具体的溢出场景假设N10^5K10^5当边长为1时一块10^5×10^5的巧克力能切出10^10个正方形这个数字远远超过int的21亿上限。就算单块巧克力没有这么大block_count的累积值也可能轻松突破int边界。解决办法很简单check函数的返回值用long long中间计算用(long long)(h[i] / x) * (w[i] / x)。注意这个强制转换的位置必须保证先转换再乘法否则两个int相乘结果先溢出为int再赋值给long long已经来不及了。这个坑我当年踩过一次本地测试小数据全对一提交大数据就WA排查了半天才发现是累加和溢出。还有一个小细节check函数里在累加过程中可以提前判断一旦cnt达到k就直接返回不需要算完所有巧克力。这是个小优化在k比较小的时候能省不少时间。虽然对于log级别的二分来说影响不大但写习惯了是好事尤其是遇到更复杂的check时。4.2 二分死循环的三种典型写法死循环问题在二分答案题里非常经典。除了上面提到的l r模板需要上取整还有几种情况会导致循环无法结束。第一种mid (l r) / 2搭配l mid。这就像是原地踏步mid可能等于l导致区间永远缩不小。解决办法是用l mid 1或者mid (l r 1) / 2。第二种边界更新条件写反。比如本题中如果check(mid)成立时你写的是r mid - 1那就会把可行解的范围往小缩最后得到一个错误答案。这种错法不会死循环但结果永远差一点而且很难通过调试发现。第三种初始上下界设置错误。如果l从0开始而答案最小是1那二分区间多了一个无意义的值虽然不影响最终结果但有可能在check(0)时出现除零错误。如果你考虑过“零”这个边界最好从1开始。4.3 手动模拟一组数据验证check逻辑为了让你对check函数有更直观的理解我们手算一组数据。假设有两块巧克力分别是3×5和4×4K3。边长从1开始试。x1时第一块能切(3/1)*(5/1) 3*5 15块第二块能切(4/1)*(4/1) 4*4 16块总共31块3可行。x2时第一块能切(3/2)*(5/2) 1*2 2块第二块能切(4/2)*(4/2) 2*2 4块总共6块3可行。x3时第一块能切(3/3)*(5/3) 1*1 1块第二块能切(4/3)*(4/3) 1*1 1块总共2块3不可行。所以最大边长是2。你会发现x3时第一块3×5的巧克力虽然面积是15但能切出的边长3的正方形只有1个因为宽度方向只有1个3长度方向5只能排1个3剩下的2被浪费掉了。这就是“边角料无法拼接”的直观例子。建议你把这个手算过程走一遍尤其是理解为什么3×5的矩形在x2时能切2块而不是面积法算出来的3块。想通了这一点check函数的本质就彻底明白了。5. 从分巧克力到一类题——二分答案的迁移套路5.1 什么时候该想到二分答案刷题多了你会发现有一类题的题眼特别明显求最大值或最小值并且答案是一个整数同时存在一个“判断某个候选值是否可行”的简单方法。这类题十有八九是二分答案。典型特征有三个第一个特征是“可行性判断比直接求解容易得多”。分巧克力就是典型直接算最大边长很难但给定一个边长判断够不够分K块却是简单的遍历。这个“给定答案验证可行性”的思路本身就是从暴力枚举演化出来的。第二个特征是“答案具有单调性”。分巧克力里边长越大块数越少这是单调递减有些题目里参数越大越容易满足条件这是单调递增。不管方向如何只要是单调函数就可以二分。第三个特征是“数据范围不友好”。如果N和K只有100暴力枚举完全可以接受但当它们来到10^5级别暴力必然超时这个信号就是在提醒你应该考虑更优算法。做题前养成估算复杂度的习惯很重要看到一个数据范围先想想暴力能不能过不能过就往二分、贪心、动态规划这些方向想。5.2 同框架题目的横向对比二分答案是一个框架套上不同的check函数就变成不同的题。分巧克力算是最直观的入门题还有几道经典题可以放在一起对比。比如“砍树”那类题有N棵树每棵树有高度要砍掉超过某个高度H的部分问H最大是多少使得砍下的总长度至少为M。这题和分巧克力的结构一模一样check函数就是遍历每棵树累加max(0, height[i] - H)判断是否 M。再比如“跳石头”那类题在一条河里有若干块石头移走其中M块使得相邻石头间最短距离最大化。这里check函数判断的是“如果最短距离为x最少需要移走多少块石头”然后看这个数量是否不超过M。表面上是最大值最小化本质还是二分答案。这几个例子放在一起能更清楚地看到二分答案的通用模板外层二分答案内层check函数解决一个判定性问题。你只要能把check函数写对后面的二分逻辑几乎是复制粘贴。所以刷题的时候我建议你不要只满足于AC一道题而是把同类题各做一遍感受check函数的各种变体这比盲目刷一百道新题都管用。5.3 我的一点刷题心得这道题我第一次提交的时候WA了一发原因是check里用了(long long)(h[i] * w[i] / (x * x))也就是面积相除的写法。当时小数据全对我一度怀疑是二分写错了后来用手算3×5的例子才意识到是check函数的问题。从那以后我遇到所有“切割”“分配”“覆盖”类的题目都会警惕是否需要用几何计数而不是面积相除。这类教训其实很值得记下来。二分答案的框架就那么大真正区分你能不能AC的是check函数的正确性。写check之前先花一分钟在草稿纸上画个小例子验证一下公式比提交上去被罚时划得来得多。分巧克力这题提供一个很好的思维锚点下次再遇到求最大最小值的题脑子里就会自动多一条“二分答案”的搜索路径。
