企业官网建设流程全解析

东华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是一个可行解，答案应该更大，因此把左边界移动到mid+1；如果不能，说明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，正方形面积4，15除以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 = 4，mid = (3 + 4) / 2 = 3，如果check(3)成立，执行l = mid后l还是3，r还是4，无限循环。加上1之后，mid = (3 + 4 + 1) / 2 = 4，就可以正常推进。

两个模板没有高下之分，我个人的体验是：第一种l <= r + ans适合新手，逻辑直白，不怕死循环，ans变量帮你兜底；第二种l < r更简洁，但上取整和边界条件需要理解透彻才敢用。如果你在比赛里写第二种模板，建议在草稿纸上把l=3, r=4这种临界情况手动推一遍，确认不会卡死再提交。

4. 实战中的常见问题与避坑记录

4.1 类型溢出：最隐蔽的WA来源

我在第1.2节提到数据范围是10^5级别，但很多人写代码的时候就是忍不住用int。这里有一个具体的溢出场景：假设N=10^5，K=10^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×4，K=3。边长从1开始试。

x=1时：第一块能切(3/1)*(5/1) = 3*5 = 15块，第二块能切(4/1)*(4/1) = 4*4 = 16块，总共31块，>=3，可行。

x=2时：第一块能切(3/2)*(5/2) = 1*2 = 2块，第二块能切(4/2)*(4/2) = 2*2 = 4块，总共6块，>=3，可行。

x=3时：第一块能切(3/3)*(5/3) = 1*1 = 1块，第二块能切(4/3)*(4/3) = 1*1 = 1块，总共2块，<3，不可行。

所以最大边长是2。你会发现，x=3时第一块3×5的巧克力虽然面积是15，但能切出的边长3的正方形只有1个，因为宽度方向只有1个3，长度方向5只能排1个3，剩下的2被浪费掉了。这就是“边角料无法拼接”的直观例子。

建议你把这个手算过程走一遍，尤其是理解为什么3×5的矩形在x=2时能切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之前，先花一分钟在草稿纸上画个小例子验证一下公式，比提交上去被罚时划得来得多。分巧克力这题提供一个很好的思维锚点，下次再遇到求最大最小值的题，脑子里就会自动多一条“二分答案”的搜索路径。