最近做周赛 430 的时候我被 LeetCode 3453“分割正方形 I”这道中等题卡了一会儿。倒不是思路多难而是题面里“正方形”这个信息太有迷惑性我一开始总想着几何图形怎么切、面积怎么算绕了不少弯路。后来把题意拉直发现它本质上是一个“把 n 切成长度尽量接近的若干段然后让两段最大值相乘”的模型题。这篇就完整梳理一下我的解题过程包括为什么均匀切割一定最优、怎么写代码、以及我在取整和边界上踩过的坑。1. 题意把“切割正方形”翻译成数学模型先说明一下我处理的题面版本。给定一个边长为n的正整数正方形你可以在整数坐标处沿水平或垂直方向切割水平切的总刀数和垂直切的总刀数加起来不能超过k。切完之后会得到若干个小矩形你需要让所有小矩形中面积最大的那个尽量小返回这个最小可能的最大面积。这里有几个关键点第一次读题很容易忽略。第一切割线必须放在整数坐标。这意味着你不可能把边长n等分成任意小数段每段长度必须是正整数。比如n 10你想切成三段那只能是3, 3, 4这样的分配不能是10/3这种带小数的长度。第二水平切割会影响每一列的高度垂直切割会影响每一行的宽度。切完之后所有小矩形共同组成一个完整的网格结构如果水平切成h 1条垂直切成v 1列那么最终就有(h 1) × (v 1)个矩形面积取决于某一行段的高度乘以某一列段的宽度。第三总刀数是h v ≤ k不是必须用满。当然为了把最大面积压下去我们通常会把刀数用满除非某一维度已经切到极限——也就是每段长度都是 1再也切不动了。把题面翻译成数学语言就是这样给定 n 和 k找非负整数 h, v满足 h v ≤ k且 h ≤ n-1, v ≤ n-1。 在水平方向把长度 n 切成 h1 段垂直方向切成 v1 段。 每段长度必须是正整数且我们希望每一维里的“最长段”尽量小。 设水平方向最长段为 A垂直方向最长段为 B则最大矩形面积 A × B。 目标是最小化 A × B。为什么这两个最长段决定了最大面积因为任意一个小矩形都是由某一段高度和某一段宽度组成的。面积最大时自然取的是最宽的那一列和最窄不对是取高度最大的那一段乘以宽度最大的那一段。所以只要把这两个最大值压住整个网格里所有矩形的面积都不会超过它们的乘积。我一开始想复杂了觉得切割方式可以是任意的不一定要形成完整的网格。比如你切一个十字再在局部切一刀就可能形成不是网格的分割结构。但后来想明白题面里说了每次切割都是贯穿当前矩形的整条线最终所有分割线要么是一整条水平线贯穿正方形要么是一整条竖直线贯穿正方形。所以最后形成的结构必然是一个网格不存在“T 字形”或更复杂的分割。这一点很关键它把几何问题直接转化成了“选择几刀水平几刀垂直”的组合问题。2. 为什么均匀分段是局部最优两个关键结论一旦确定了h和v接下来要解决的是在水平方向切h刀也就是把长度n分成h 1段怎么分才能让最长的那段最短答案不是“随便分”也不是“把刀都集中在一边”而是均匀分。结论一把正整数n分成m段每段长度均为正整数时可能达到的最小最大段长是⌈n / m⌉也就是ceil(n / m)。这个结论的证明不难。如果所有段长度都小于等于x那么m段的总长度最多是m × x必须满足m × x ≥ n所以x ≥ n / m。因为x必须是整数所以x ≥ ceil(n / m)。反过来只要允许段与段之间长度最多差 1就一定可以构造出每段长度要么是⌊n/m⌋要么是⌈n/m⌉的分法因此上界也能达到。举个例子n 10, m 3ceil(10/3) 4。可以分成4, 3, 3最大段长正好是 4。n 10, m 4ceil(10/4) 3分成3, 3, 2, 2最大段长是 3。如果你分成5, 2, 3这种不均匀的最大段长变成 5显然更差。结论二在总刀数固定的情况下水平刀数和垂直刀数之间有一个“平衡”问题。垂直方向能切多少刀不只看剩余刀数还要看n的物理上限。比如h定死了剩余刀数k - h可以给垂直方向。如果k - h n - 1那垂直方向最多只能切n - 1刀因为再切就变成 0 长度的段了没有意义。所以垂直刀数应该取v min(k - h, n - 1)。这里有个细节为什么要把所有剩余刀数都给垂直方向因为垂直刀数越多列的段数越多ceil(n / (v1))会越小至少不会变大。所以对于固定的hv取最大总是最优的哪怕留在手里不用也比用掉差。这一点是贪心思想用在这里是对的因为每一维内部的切割互不影响多切一刀只可能降低或维持该维的最大段长。有了这两个结论问题就变成一个单变量枚举遍历h从0到min(k, n-1)每次计算对应的v然后计算最大面积取全局最小。我用一组小数据验证过。n 5, k 2h 0, v 2水平 1 段长度 5垂直 3 段最大长度ceil(5/3) 2面积5×2 10h 1, v 1水平 2 段最大长度 3垂直 2 段最大长度 3面积3×3 9h 2, v 0水平 3 段最大长度 2垂直 1 段长度 5面积2×5 10最优是 9也就是一刀横、一刀竖切成四块最大那块是3×3。这符合直觉刀数少的时候横竖均衡比单方向猛切更优。再比如n 5, k 3遍历之后最优是 6对应h 1, v 2或h 2, v 1。你能切出一个3×2的矩形最大面积就是 6。单方向切三刀的话比如h 0, v 3垂直方向 4 段最大长度 2水平方向只有 1 段长度 5面积还是 10差很多。3. 遍历水平刀数O(k) 解法与代码实现数学模型清楚了代码其实很短。但有几个点必须注意否则很容易在小数据上出错。先说最常规的枚举实现思路。h的取值范围是0到min(k, n-1)因为水平方向最多切n-1刀再多没有意义。对于每个h剩余垂直刀数v min(k - h, n - 1)但还要保证v 0。然后计算两个最大段长。计算ceil(n / m)不要直接用浮点数避免精度问题。推荐用整数公式(n m - 1) // m。下面是我写的 Python 版本可以直接跑def min_max_area(n: int, k: int) - int: # 如果刀数足够把每一维都切成 1 单位答案就是 1 if k 2 * (n - 1): return 1 ans n * n # 一口都不切最大面积就是整个正方形 # 枚举水平方向切多少刀 for h in range(0, min(k, n - 1) 1): # 剩余刀数尽量给垂直方向 v k - h if v n - 1: v n - 1 if v 0: continue rows h 1 # 水平分出的条数 cols v 1 # 垂直分出的列数 max_row_len (n rows - 1) // rows max_col_len (n cols - 1) // cols ans min(ans, max_row_len * max_col_len) return ans边界情况我已经在代码里处理了。你可能会问为什么一开始if k 2 * (n - 1)直接返回 1因为水平方向最多能切n-1刀垂直方向也最多能切n-1刀。当总刀数达到2n - 2时两个方向都切到了最细每一格都是1×1最大面积必然是 1不可能更小。这个剪枝在k很大的时候非常关键否则枚举会退化成O(n)甚至超时。如果不用这个剪枝比如n 100000, k 100000枚举范围是0到min(100000, 99999)也就是十万轮其实也能接受。但加上剪枝后很多测试用例可以瞬间返回。再看一个容易忽略的问题枚举h的时候v min(k - h, n - 1)这意味着当k - h大于n - 1时垂直方向已经切满了多余的刀数被丢弃。这时继续增大hv保持不变面积会随着h的增大单调不增。比如n 100, k 150当你枚举到h 52以后v一直是99再多水平刀只会让行变多、最大行高变小乘积不可能变大。所以虽然我们枚举了所有h但真正可能形成最优解的范围其实不大。我还测试了几组边界值n 1, k 0k 2*0成立返回 1。正确因为只有一个 1×1 正方形。n 1, k 5虽然刀数足够但物理上切不了返回 1。正确。n 6, k 1枚举h0时v1面积6×318h1时v0面积3×618。答案 18。因为只切一刀最多把一个维度分成两段最大段长是 3另一个维度还是 6乘积是 18。n 10, k 4最优是h2, v2水平 3 段最大长ceil(10/3)4垂直 3 段最大长 4面积 16。如果h1, v3水平 2 段最大长 5垂直 4 段最大长 3面积 15 反而更小。所以最优不一定是横竖几乎相等要小心。从最后一组可以看出h和v的“均衡”不是简单的数量相等因为ceil(n/(h1))是阶梯函数不一定连续对称。这也是为什么不能直接猜h k//2必须枚举或者做优化。4. 边界情况与整数陷阱实测最容易错的点写这道题的时候我最开始用的是浮点数结果有边界直接翻车。比如n 1000000000ceil(n / 3)用n / 3算可能得到 333333333.333再int()一下变成 333333333但正确结果是 333333334。所以后来我全部改成整数除法。取整公式(n m - 1) // m适用于所有正整数m但当m 0时要先叉掉。代码里rows h 1cols v 1只要h 0、v 0就不可能除零这个还好。另一个大坑是“刀数上限”的语义。垂直方向最多切n - 1刀但当你v n - 1时cols n每一列宽度是 1。这时候再增大hv不会变。但如果你枚举时不限制v的上限而是直接把v k - h当v远大于n-1时cols v1会大于nceil(n / cols)恒等于 1看起来好像没问题但实际含义是“把一个只有 n 行的正方形切成超过 n 列”这是物理上不可能的。虽然面积计算结果还是对因为多于 n 列时宽度的最大值仍然是 1但会在思维上造成混乱导致后续推导出错。我建议代码里始终保留v min(k - h, n - 1)让变量含义始终合法调试的时候不容易懵。还有一点初始化ans时如果n达到10^9ans n * n就是10^18在 C 里要用long longPython 无所谓但在 Java/C 里这是最常见的溢出点。就算题目说答案不会超过某个范围我在写ans初始值的时候也习惯直接用一个大数比如10^30或者LONG_MAX避免边界计算冲突。再说“是否可以不用满所有刀”这个问题。我一开始以为总刀数必须等于k所以在枚举时要求h v k结果当k很大的时候被迫把一刀切到没意义的地方答案反而偏大。后来意识到题面是“不超过 k 刀”不是“恰好 k 刀”。当我们已经把一个维度切到底之后多余的刀数应该直接丢掉。这也是为什么用min(k-h, n-1)而不是强制用完。还有一个比较隐蔽的细节关于“均匀分段”在实际切割中的可构造性。比如n 7, m 3ceil(7/3) 3可以分成3, 2, 2没问题。但如果n 7, m 4ceil(7/4) 2分成2, 2, 2, 1最大段长 2没问题。只要m n总能构造出每段长度差不超过 1 的分法。如果m n那就必须限制因为段数不能超过单位长度个数。我在周赛实际提交的时候有一版没加k 2 * (n - 1)的剪枝遇到n 100000, k 1000000000这种数据直接死循环因为range(0, min(k, n-1)1)虽然只有十万次但当时我把v上限写错了导致内部有重复计算其实还好。后来加上剪枝代码立刻干净利落。最后总结一下我认为这题最值得记住的点遇到“把 XX 切成若干块”的题目第一反应不是想怎么画线而是先抽象成“横纵两个维度分别分成几段”。只要能把两段最长长度相乘的最小值求出来题目就变成了一维枚举或三分。这道题虽然标着中等但如果能快速建模写代码的时间其实不到十分钟。