1. 一道经典二分题为什么值得单独拿出来讲备战蓝桥杯的同学基本都绕不开这道分巧克力。省赛填空题和编程题里它是典型的二分答案模板题只要练过一遍省赛遇到类似题基本就是送分。但每年还是有不少人在它上面翻车——不是不会二分而是check函数写错、左右边界没想明白、或者被输入输出的小细节卡住白白丢分。先说这道题的背景。题目出自蓝桥杯省赛C/C组大意是有N块巧克力形状都是矩形第i块的长宽分别是H_i和W_i。现在要把所有巧克力都切成边长是整数的正方形小块要求切出来的所有小块必须大小相同也就是边长统一为某个整数K。切的时候每一块矩形都要独立切成若干K×K的正方形不能拼接、不能剩余边角料再凑一块。问题是最多能切出多少块但题目通常会反着问如果至少要切出M块那么K的最大值是多少。我当年第一次做的时候上来就想暴枚边长从1枚举到最大边长对每个边长去算能切几块直到块数小于M为止。这个思路本身没错但如果N和M的数据范围拉到10^5级别单块边长范围又是10^5级别三层循环直接炸掉。用二分把枚举边长从O(maxLength)优化成O(log maxLength)这道题的复杂度就变成了O(N log L)稳过。这篇文章就围绕这道题讲透三件事怎么把题意转化成二分模型、check函数怎么写才不容易错、以及省赛实战里那些容易被忽视的细节。无论是C/C组还是Java/Python组核心思想完全通用。2. 题面拆解与暴力复杂度账本2.1 一块矩形能切出多少块正方形先搞清楚最基本的数学关系。假设一块矩形的长是H、宽是W要切成边长为K的正方形不考虑摆放方向时沿长边能切出floor(H/K)个沿宽边能切出floor(W/K)个总块数就是两者相乘块数 (H / K) * (W / K)这里全部是整数除法。我见过有同学写成(H * W) / (K * K)这是错的。因为正方形的摆放是离散的网格对齐不能把面积直接相除。举个例子就明白了一块3×3的矩形K2时按公式应该是(3/2)(3/2)111块而按面积算是9/42.25块实际当然只能切出1块2×2的正方形剩下1行1列都是废料。再把所有块加起来就得到在边长K下全部巧克力总共能切出的块数SS sum((H_i / K) * (W_i / K))i 1..N题目要求的每人至少分到一块等价于要求S M。2.2 暴力做法的复杂度账如果不做二分最直观的暴力枚举方案是从K1开始一直枚举到所有巧克力中长和宽的最大值maxL对每个K累加一遍总块数找到最大的K使S M。假设N10^5maxL10^5每个K算一次需要遍历N块巧克力总操作量是10^5 × 10^5 10^10次。这在蓝桥杯的评测环境下C大概需要几十秒Java和Python更不用想妥妥超时。暴力复杂度是O(N × L)二分答案能把复杂度降到O(N × log L)其中log L在maxL10^5时大约只有17。两者差距是数量级的。2.3 为什么这道题具有单调性二分能用的前提是答案具备单调性。分巧克力题里的单调性很直观K越大每块正方形越大能切出的块数越少K越小正方形越小切出的块数越多。翻译成数学语言设f(K)表示边长为K时的总块数那f(K)是随K增大而单调不增的函数。如果某个边长K0能满足f(K0) M那么所有比K0小的边长也一定能满足反过来如果K0不满足那所有比K0大的边长也都不满足。这样就形成了一条分界线小的那边全都满足大的那边全都不满足我们要找的就是满足条件的最大K也就是这条分界线的右端点。这种模型在算法里叫最大值最小化或者最小值最大化的变体本质上都是在单调函数上做二分查找。3. 二分模型的建立与check函数的设计3.1 二分查找的区间定义很多人写二分题头疼是因为区间定义不清。我先把我自己习惯的定义写出来后面所有代码都基于这个定义。low左边界初始化为1。这是合法边长的下界因为题目要求边长是正整数K至少是1。high右边界初始化为所有巧克力中max(H_i, W_i)的最大值。因为边长不可能超过最大矩形边否则连一块都切不出来。循环条件while (low high)注意是小于而不是小于等于。中点mid (low high 1) / 2。这里为什么要加1下面细说。每次取mid去check如果check(mid)为true说明边长mid可以切够M块那答案可能在mid或者比mid更大的位置所以low mid如果check(mid)为false说明mid太大了答案一定小于mid所以high mid - 1。当low high时low就是最终答案。3.2 中点加1的原因防止死循环关于mid的取法这里有个经典坑。如果写成mid (low high) / 2配合low mid这个更新在某种特定情况下会陷入死循环。举个例子low2high3此时如果check(2)为true按公式mid(23)/22然后lowmid2循环条件23仍然成立再次计算mid还是2low还是2无限循环。解决方法是让中点偏右mid (low high 1) / 2。同样low2、high3的情况下mid(231)/23如果check(3)为truelow3循环退出如果check(3)为falsehigh3-12lowhigh也退出。一句话总结如果更新方式是lowmid那mid就要取右中位数加1如果更新方式是highmid那mid可以取左中位数不加1。两种更新方式和两种取法必须配对混用就是死循环。3.3 check函数的实现细节check函数本身不复杂就是遍历所有巧克力累加块数看最终值是否大于等于M。代码如下bool check(int k) { long long total 0; for (int i 0; i n; i) { total (h[i] / k) * (w[i] / k); if (total m) return true; // 提前退出避免无谓计算 } return false; }这里有两个细节值得注意。第一total要用long long。单块最多能切出的块数是(10^5/1)×(10^5/1)10^10如果还是int直接溢出变负数这种错在比赛里非常隐蔽因为你肉眼很难从一堆数字里发现是符号位出了问题。第二尽早返回。total一旦超过M就没必要继续遍历了直接return true。别小看这个优化当K很小时可能前几块就够M了能省下大半遍历时间。相反的情况如果遍历完了还没到Mreturn false。3.4 main函数完整写出下面给一个完整的C实现直接用数组存每块巧克力的长和宽#include bits/stdc.h using namespace std; const int MAXN 100005; int h[MAXN], w[MAXN]; int n, m; bool check(int k) { long long total 0; for (int i 0; i n; i) { total (long long)(h[i] / k) * (w[i] / k); if (total m) return true; } return false; } int main() { cin n m; int maxLen 0; for (int i 0; i n; i) { cin h[i] w[i]; maxLen max(maxLen, max(h[i], w[i])); } int low 1, high maxLen; while (low high) { int mid (low high 1) / 2; if (check(mid)) { low mid; } else { high mid - 1; } } cout low endl; return 0; }这里high直接取了maxLen没有额外加1。因为check(maxLen)在最坏情况下也可能返回false但二分框架会把high不断压下来不影响正确性。4. 边界条件与实战中容易踩的坑4.1 输入结束符与多组测试数据蓝桥杯的题目一般来说是单组数据但有些模拟赛或改编题会放多组测试数据。我见过不少同学在本地跑没问题一提交就超时或者WA最后发现是读入方式不对。如果题目明确说输入包含多组测试数据以EOF结束就要这样写while (cin n m) { // 每组数据要重新初始化maxLen和数组 }如果maxLen在循环外定义记得每组数据都要重置。建议把每一轮的处理逻辑封装成函数避免变量残留。4.2 巧克力数据可能非常不均匀有些测试点会故意把数据设计成极端情况比如有一块巧克力特别大其余都很小。这时候maxLen会很大二分次数也就多一点但log2(10^5)只有17次完全不用担心。真正要担心的是check函数里total的累加顺序。如果先累加了很多大巧克力total很快超过M就会提前return true这没问题。如果大巧克力放在最后面前面的小巧克力累加很慢但全部遍历完也就N次问题不大。所以不需要对巧克力排序保持输入顺序即可。4.3 K1的情况为什么总是满足注意K1时任何巧克力都能切成H×W块总数Ssum(H_i×W_i)肯定远大于M因为M的人数不会超过巧克力总块数——题目给出的合法数据必然如此。所以low初始化为1是有保证的至少存在一个可行解。这也说明答案一定存在不需要额外判断。反过来想如果题目数据保证所有人能分到巧克力那K的最小值一定不小于1二分区间从1开始是安全的。4.4 分巧克力的变种问法蓝桥杯这道题偶尔会改头换面考你。比如把正方形改成等腰直角三角形、等边三角形形状的小块实际还是矩形或者改成每个人分到的巧克力必须来自同一块原巧克力。后面这种变体的check函数就不一样了因为同一块巧克力切出来的块数必须一次性分给同一个人而不是把不同巧克力的零头拼一起。如果遇到这种变体check函数的逻辑要改成对于第i块巧克力它能切出的块数cnt (h[i]/k) * (w[i]/k)这些块只能满足cnt个人的需求真实有效块数就是cnt本身不会因为别的巧克力多出来而改变。核心还是二分但判定逻辑变了不要照搬模板。5. Java和Python版本的关键差异5.1 Java版实现与注意点Java选手写这道题有几个地方容易吃亏。一是整数除法没问题但要小心int乘法溢出二是Scanner读入10^5规模的数据再加上10^4规模的输入直接System.out.println输出会很慢建议用StringBuilder收集答案一次性输出。import java.util.*; public class Main { static int[] h, w; static int n, m; static boolean check(int k) { long total 0; for (int i 0; i n; i) { total (long)(h[i] / k) * (w[i] / k); if (total m) return true; } return false; } public static void main(String[] args) { Scanner in new Scanner(System.in); n in.nextInt(); m in.nextInt(); h new int[n]; w new int[n]; int maxLen 0; for (int i 0; i n; i) { h[i] in.nextInt(); w[i] in.nextInt(); maxLen Math.max(maxLen, Math.max(h[i], w[i])); } int low 1, high maxLen; while (low high) { int mid (low high 1) / 2; if (check(mid)) low mid; else high mid - 1; } System.out.println(low); } }用BufferedReader替代Scanner能进一步提速但写起来繁琐一些。对于这道题的数据量Scanner足够用没必要在比赛里花时间搞复杂IO。5.2 Python版实现与性能优化Python的写法很简洁但容易在性能上栽跟头。同样10^5的数据量Python纯循环跑满10^5 × 17 1.7×10^6次其实不算大。但如果用for循环函数调用Python的常数开销会让时间超出很多人因此TLE。建议把check写成内联逻辑或者尽量用列表推导。最省事的做法是在二分循环里直接遍历列表不要额外调用函数因为函数调用在Python里开销不小。n, m map(int, input().split()) chocolates [tuple(map(int, input().split())) for _ in range(n)] max_len max(max(h, w) for h, w in chocolates) low, high 1, max_len while low high: mid (low high 1) // 2 total 0 for h, w in chocolates: total (h // mid) * (w // mid) if total m: break if total m: low mid else: high mid - 1 print(low)这里我专门把break提前放在for内部和C版本里提前return对应实测能省不少时间。还有一点使用sys.stdin.buffer.read()一次性读取所有输入在数据量大时比input()逐行读快很多省赛如果担心性能可以考虑这个替代方案。6. 从分巧克力到一类题的举一反三6.1 二分答案题型的识别特征做多了你会发现分巧克力其实是二分答案大类里的经典代表。这类题有很明显的识别特征求最大值最小或最小值最大答案具备单调性直接枚举会超时但判定某个答案是否可行比较容易常见的同类题目还有木材加工把木头切成等长小段求最大长度、跳石头移走若干石头后求最短跳跃距离的最大值、围栏刷漆之类。它们的共性就是把找答案转换成猜答案验证答案。识别出二分答案模型后剩下的工作基本上是机械的确定上下界、设计check函数、套二分模板。所以刷题时看到这类题要有意识地训练自己快速识别题型的能力而不是真的从零开始推。6.2 check函数的设计思路从问题出发而不是从代码出发很多人写check函数容易陷入直接翻译题意的陷阱缺少一层转化。分巧克力这题的转化很简单矩形切成正方形用整除算块数。但有些题需要更深的转化。比如跳石头的check函数不是问能不能移走M块石头而是问如果最短跳跃距离至少是d那么最少需要移走多少块石头然后看这个最少移走数量是否超过M。这就是把可行性验证转化为贪心计数。分巧克力这道题之所以推荐作为入门模板正因为它的check函数几乎没有转化成本适合新手先建立二分模板的肌肉记忆再去练习更复杂的转化。6.3 二分模板的三种变式小结我根据这些年的刷题经验把二分答案的模板整理成三种场景分巧克力属于第二种场景二分框架中点公式更新方式找满足条件的最大值右边界lowhigh(lowhigh1)/2lowmid, highmid-1找满足条件的最小值左边界lowhigh(lowhigh)/2lowmid1, highmid查找精确值lowhigh(lowhigh)/2根据比较结果移动分巧克力是第一种。重点记一下只要更新里有lowmid就用右中位数只有highmid用左中位数。别混。6.4 省赛现场的做题策略真到了蓝桥杯省赛的考场上我建议这样对待分巧克力这类模板题前5分钟用来读懂题、抽象模型、确定是二分这比马上动手写代码更重要。很多人在没想清楚check函数时就开写结果改来改去浪费时间。写代码时直接把long long用上别贪省事用int。数据范围没看仔细就写int是省赛最常见的丢分原因。在草稿纸上算一遍样例的二分过程手动跑一遍low和high的变化轨迹确认不会死循环。如果时间充足顺手构造一个边界测试比如N1、M1、单块极大巧克力的数据确保输出正确。7. 完整代码、复杂度分析与本地验证方法7.1 C完整代码含输入加速和注释为了直接在蓝桥杯环境下提交不出问题这里给一个带输入输出加速的完整版本#include bits/stdc.h using namespace std; const int MAXN 100005; int h[MAXN], w[MAXN]; int n, m; bool check(int k) { long long total 0; for (int i 0; i n; i) { total (long long)(h[i] / k) * (w[i] / k); if (total m) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; int maxLen 0; for (int i 0; i n; i) { cin h[i] w[i]; maxLen max(maxLen, max(h[i], w[i])); } int low 1, high maxLen; while (low high) { int mid (low high 1) / 2; if (check(mid)) { low mid; } else { high mid - 1; } } cout low \n; return 0; }7.2 复杂度分析二分次数O(log L)其中L是最大边长L 10^5所以大约17轮。每轮check遍历N块巧克力O(N)。总复杂度O(N log L)约为10^5 × 17 1.7×10^6次运算。空间复杂度O(N)只用两个数组存长和宽。7.3 本地测试的方法我习惯在本地写一个随机数据生成器来验证二分逻辑。比如直接用下面这个Python脚本生成测例然后和暴力枚举的结果对比import random n random.randint(1, 20) m random.randint(1, 200) print(n, m) for _ in range(n): h random.randint(1, 100) w random.randint(1, 100) print(h, w)然后写一个暴力版本n, m map(int, input().split()) chocolates [tuple(map(int, input().split())) for _ in range(n)] max_len max(max(h, w) for h, w in chocolates) ans 1 for k in range(1, max_len 1): total sum((h // k) * (w // k) for h, w in chocolates) if total m: ans k print(ans)两个程序跑同样数据答案一致就说明二分实现没问题。这种对拍方法能抓出绝大多数边界bug强烈建议比赛前养成习惯。7.4 一个易错点的复盘最后复盘一个我当年真实犯过的错。我最早写这题时check函数里用了total (h[i] / k) * (w[i] / k)没加long long强转。C里两个int相乘即使结果超出int范围运算仍然在int域内进行得到溢出值后才赋给long long此时已经晚了。后来改成(long long)(h[i] / k) * (w[i] / k)就再没出过问题。这个教训可以泛化成一条通用原则在C/C里任何两个int相乘前只要乘积可能超过约2.1×10^9就要先强转为long long再说。这道题因为K最小为1单块块数最大能到10^5×10^510^10显然必须转。别指望编译器帮你处理它不会。