递增代价下的二分答案：LeetCode 3296移山秒数与可行性检查详解

看到“移山所需的最少秒数”这个题号3296的时候我第一反应是又一个披着模拟外壳的二分答案题但真正动笔写check函数时才发现坑全藏在一个很不起眼的细节里每个工人的耗时是按第几次操作递增的而不是固定的。很多人卡在这个题上不是因为不会二分而是因为没把“第k次操作耗时k倍递增”这个数学模型理清楚。这篇就把从读题到AC的完整思路写出来包含我踩过的浮点精度坑、上界选择坑以及一个可以用来验证的完整手算样例希望能帮你彻底弄懂这类“并行任务递增代价”的二分答案题。1. 先别急着模拟把问题变成一道判断题1.1 题面里的隐藏模型第k次操作的耗时按k倍递增题目说的是有mountainHeight个单位高度要移走每个工人i完成第k次操作需要workerTimes[i] * k秒。这句话是整道题的关键也是最容易读错的地方。很多类似题比如“完成旅途的最少时间”里每个工人完成一次操作的耗时是固定的check 的时候直接T // workerTimes[i]就能算出该工人能完成几次。但本题不是这样。一个工人完成第1次操作要w秒完成第2次要2w秒完成第3次要3w秒。也就是说如果他总共完成了k次操作那么他的总耗时是w * (1 2 3 ... k) w * k * (k 1) / 2这是一个等差数列求和公式也是整个check函数的数学基础。我习惯把这个过程类比成打包包裹每多打一箱体力消耗越大所以后续箱子花费的时间越来越长。工人并不是恒定速度工作的而是越干越慢。这个递增模型直接决定了你不能用简单的“总工作量除以总速度”去算答案——工人之间的能力和疲劳曲线都不一样答案只能靠搜索。1.2 为什么模拟是死路规模与单调性拿到这个题第一反应可能是模拟每秒挑一个当前最快完成下一次操作的工人去移一个单位高度。如果mountainHeight很小这样当然可以但题目里的山高可以到极大完全模拟一次操作的时间复杂度是O(mountainHeight * n)这显然不可行。更本质的问题是我们根本不需要关心“具体是哪一秒哪个工人动了手”只需要知道“给定一个总时间 T所有人合起来能不能把山移完”。这是一个典型的可行性判定问题。而这个判定满足单调性给的时间越多工人能完成的操作次数只会更多所以“能在 T 秒内完成”这个命题从 False 到 True 只有一次翻转。既然单调就可以二分答案。二分答案的核心不是去模拟过程而是把一个“求最值”的问题转换成“给定一个值判断可不可行”的问题。2. 二分答案把“最少秒数”拆成“可行性检查”2.1 二分答案的通用套路二分答案这类题有一个固定节奏我总结成三步确定二分对象本题我们二分的是总秒数 T也就是最终答案。设计可行性检查函数check(T)判断所有工人在 T 秒内能否累计移走mountainHeight个单位高度。根据单调性收缩区间如果check(T)为 True说明 T 秒够用答案不会比 T 更大所以把上界收缩到 T如果为 False说明 T 秒不够答案一定大于 T所以把下界提高到 T 1。这里有一个容易混淆的点二分的是“答案”不是“数组下标”。所以在写循环条件时要时刻提醒自己mid表示的是秒数而不是某个工人的操作次数。外层二分框架大概是这样的lo 1 hi 一个足够大的上界 while lo hi: mid (lo hi) // 2 if check(mid): hi mid else: lo mid 1 return lo只要check写对了这个框架可以直接套用。真正的难点全在check内部。2.2 核心check函数解一个一元二次不等式check(T)要做的事情很清晰对每个工人算出他在 T 秒内最多能完成多少次操作然后累加判断总和是否达到mountainHeight。关键在于“算单个工人在 T 秒内最多能完成多少次操作”。由前面的公式工人 i 完成 k 次操作需要workerTimes[i] * k * (k 1) / 2 T移项一下问题变成给定 T 和 w求最大的整数 k满足k * (k 1) / 2 T / w这里我习惯先令m T / w整数除法然后解一元二次不等式。注意这个整数除法是安全的因为左边k*(k1)/2一定是整数所以“它不超过T/w”等价于“它不超过T/w的整数部分”。解这个不等式有两种常见做法第一种直接用求根公式取整然后微调由k*(k1)/2 m可得k floor((sqrt(8*m 1) - 1) / 2)这个公式本身没问题问题出在浮点数的精度上。当m大到一定程度sqrt返回的浮点数可能差出 1所以必须要做一步“回修”计算(k1)*(k2)/2 m是否成立如果成立就k再检查k*(k1)/2 m如果成立就k--。这个修正循环最多执行一两次几乎不影响性能。第二种对 k 做整数二分既然k*(k1)/2关于 k 单调递增那么也可以对单个工人的 k 做二分。上界不需要拍脑袋可以直接取isqrt(2*m) 1因为最优 k 一定满足k*(k1)/2 m所以k sqrt(2*m)。这个上界精确且安全。我个人在 C 里常用第一种公式 修正在 Python 里更喜欢第二种因为math.isqrt给出的是精确整数平方根没有浮点误差配合二分写起来很稳。不管用哪种check 里都还有一个值得注意的小优化每累加完一个工人的贡献就立刻判断是否已经达到mountainHeight达到了直接返回 True后面的人就不用算了。这既能省时间也能避免累加值过大带来的心理负担。2.3 手算示例mountainHeight4, workerTimes[1,2]文字讲再多不如手算一个例子。假设山高是 4两个工人的workerTimes分别是 1 和 2。先看 T 3工人1的m 3 / 1 3解k*(k1)/2 3k 最大是 2因为 23/2334/263。工人2的m 3 / 2 1解k*(k1)/2 1k 最大是 1因为 12/2123/231。两人合计 3小于 4所以 3 秒不够。再看 T 5工人1仍然是 2 次工人2的m 5 / 2 2解k*(k1)/2 2k 最大是 1因为 2*3/232。合计还是 3不够。最后看 T 6工人1的m 6k 最大是 334/26。工人2的m 6 / 2 3k 最大是 223/23。合计 5已经大于等于 4所以 6 秒可行。因此答案是 6。这个例子我会在写完代码后直接用来做本地验证比空想清楚得多。3. 完整代码与细节优化3.1 C17 实现我先把 C 版本贴出来用的是“公式求根 修正”的写法这样性能最好check 内部每个工人都是 O(1)class Solution { public: long long minimumSeconds(int mountainHeight, vectorint workerTimes) { auto can [](long long T) - bool { long long total 0; for (int w : workerTimes) { long long m T / w; long long k (sqrtl(8.0L * m 1) - 1) / 2; while ((k 1) * (k 2) / 2 m) k; while (k * (k 1) / 2 m) --k; total k; if (total mountainHeight) return true; } return false; }; long long lo 1; long long hi 1; while (!can(hi)) hi * 2; while (lo hi) { long long mid lo (hi - lo) / 2; if (can(mid)) hi mid; else lo mid 1; } return lo; } };几个细节说明一下返回值类型是long long二分区间和total也都用long long否则大样例直接溢出。sqrtl是long double版本的平方根比sqrt精度更高适合这种大整数场景。但即使这样也要配合两个while修正。外层上界我用的是倍增扩张hi从 1 开始只要can(hi)为 False 就翻倍。这样完全不需要关心答案的理论上限也避免了“上界开太大导致二分轮次过多”的问题。3.2 Python3 实现Python 没有long long的烦恼整数可以无限大所以可以更放心地使用整数二分求单个工人的 k。我用math.isqrt求精确整数平方根from math import isqrt class Solution: def minimumSeconds(self, mountainHeight: int, workerTimes: List[int]) - int: def can(T: int) - bool: total 0 for w in workerTimes: m T // w lo, hi 0, isqrt(2 * m) 1 while lo hi: mid (lo hi 1) // 2 if mid * (mid 1) // 2 m: lo mid else: hi mid - 1 k lo total k if total mountainHeight: return True return False lo, hi 1, 1 while not can(hi): hi * 2 while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 return lo注意内层二分我是往上取整的写法mid (lo hi 1) // 2并且条件满足时lo mid不满足时hi mid - 1。这是“查找满足条件的最大值”的标准写法和“查找满足条件的最小值”正好相反别搞混。3.3 上界怎么取倍增扩展很多二分答案题的上界可以直接用数学公式算出来比如“最快工人独立完成所有工作的时间”。但本题的答案范围可能非常大公式不一定好估算而且如果你对约束条件不熟悉很容易开小。所以我更推荐倍增扩张上界hi 1 while not can(hi): hi * 2这个做法的正确性依赖单调性既然答案存在且有限那么hi不断翻倍总有一刻会超过答案。从 1 倍增到 1e18 只需要大约 60 次can调用代价非常小。用倍增上界还有一个好处下界可以直接从 1 开始不用费心考虑lo的初始值。如果mountainHeight为 1答案其实等于min(workerTimes)但二分完全能自己收敛到正确值不需要特判。3.4 复杂度与提前截断外层二分答案的范围是[1, ans]迭代次数是O(log(ans))每次check遍历所有工人每个工人内部在 C 版本是 O(1)公式 常数次修正在 Python 版本是 O(log(sqrt(m)))。所以总复杂度大约是C: O(n * log(ans)) Python: O(n * log(ans) * log(sqrt(m)))n是工人数量m是单个工人对应的时间比例。Python 由于内层多了对 k 的二分常数会大一些但依然能过题。我在can里加了提前返回if (total mountainHeight) return true;这个不是可有可无的优化。当mountainHeight比较小而n很大时可能算到第三个工人就已经够了后面几千个工人完全不用再算。更重要的是它避免了total在极端数据下累加到一个非常大的值——虽然long long通常也够但能少操一份心就少操一份心。4. 边界条件与易错点排查4.1 二分区间的端点陷阱二分的端点是最容易翻车的地方我总结三个关键点第一lo从 0 还是从 1 开始如果mountainHeight 1那么至少需要移走一个单位高度最少耗时不可能低于 1 秒所以从 1 开始是安全的。从 0 开始也能跑但没必要。第二check(mid)为 True 时为什么要让hi mid而不是hi mid - 1因为mid本身就是一个可行答案答案可能是mid本身不能把它排除掉只有在check(mid)为 False 时mid才确定不是答案才能lo mid 1。第三如果倍增上界的起点hi1恰好一开始就满足can(hi)说明答案就是 1这时外层while仍然会把lo和hi收敛到 1不会出错。4.2 整数溢出问题C 里最大的隐患就是乘法溢出。k * (k 1)在 k 稍微大一点时就可能超过int范围所以必须用long long。我见过不少人在这里写出long long k (sqrt(...) - 1) / 2; while ((k 1) * (k 2) / 2 m) k;其中(k1) * (k2)两个long long相乘如果 k 接近 1e9乘积接近 1e18还在long long范围内但如果 k 更大比如 4e9乘积就会爆掉。所以更稳妥的做法是用__int128临时计算或者像 Python 那样依赖大整数。我常用的一个规避办法是在判断时先除后乘(k 1) * (k 2) / 2 m等价于判断(k1)与(k2)的乘积除以 2 是否不大于 m。如果担心溢出可以写成(long double)(k 1) * (k 2) / 2 m或者干脆用__int128。在 LeetCode 的 C 环境下__int128是可用的。4.3 浮点精度问题这是我最想强调的一个坑。sqrtl(8.0L * m 1)算出来的结果可能是一个非常接近整数的浮点数但由于 IEEE 754 浮点数无法精确表示所有大整数结果可能偏大或偏小 1。如果不做修正k可能算错导致单工人贡献多算 1 次或少算 1 次最终答案错。修正的写法我已经在代码里给了算完k之后用整数的while循环把 k 拉到正确位置。这两个循环一定要放在检查条件里while ((k 1) * (k 2) / 2 m) k; while (k * (k 1) / 2 m) --k;如果你用的是 Python直接用math.isqrt做整数平方根再配合二分求 k就完全绕开了浮点精度问题。这也是为什么我在 Python 版本里没有用求根公式的原因——不是不能而是没必要冒险。4.4 易错点速查表错误类型典型表现修复方法二分区间搞反答案差 1 或死循环明确check(mid)True 时收缩上界False 时提升下界上界开太小大样例 WA改用倍增扩张上界浮点求根精度不足小样例对、大样例错公式法必须加修正循环或改用整数二分乘法溢出C 出现负数或异常使用long long必要时__int128或先除后乘单个工人工时看成固定耗时样例直接不对记住公式w * k * (k 1) / 2check 不提前截断性能变差累加超过mountainHeight立刻返回 True5. 变体如果每次操作耗时固定问题会简单多少5.1 线性模型与递增模型的对比把本题和另一类“完成旅途的最少时间”放在一起看会很有意思。那类题目里每个工人完成一趟的耗时是固定的workerTimes[i]问完成总趟数需要的最少时间。check 就变成了total sum(T // workerTimes[i]) return total target整个 check 只有一行核心逻辑连内层二分都不用。而本题因为“第 k 次操作耗时 k 倍递增”单个工人的产能计算从除法变成了解二次不等式。对比一下两个模型模型单个工人完成 k 次操作的耗时check 里单工人产能的求法固定耗时w * kT // w递增耗时w * k * (k 1) / 2解二次不等式如果你先做了线性模型的题再来做本题一定要提醒自己不是所有并行任务都是恒定速度读题时看到“第几次操作”这种字眼就要警惕。5.2 同一套路在并行调度题中的推广本题的解法本质是“给定时间计算总产能”这在很多并行调度问题里都是通用思路。比如一批订单要分给多个加工厂每个工厂加工第 n 件产品的成本递增或者一批数据要分给多个计算节点每个节点的算力随时间衰减。只要满足“时间越多总产能越多”的单调性就可以用二分答案把最优化问题转化为判定问题。我自己做这类题的一个心得是先别急着想最优策略先想“如果给我 X 时间我能不能完成任务”。这个反向思考往往比正向模拟简单得多。很多看似复杂的调度问题一旦转成可行性判定就只剩一个数学公式的事。6. 我的做题心得与避坑经历最后聊点实操层面的东西。我第一次做这个题时直接套了固定耗时模型的 check写完样例都过不了回头仔细读题才发现“第 k 次操作耗时 k 倍”这个条件。这个教训让我养成一个习惯拿到并行任务题第一件事是确认单工人的代价函数是线性还是递增。第二次写的时候我用sqrt求根小样例全过提交后在大数据上 WA 了好几次。排查了很久才发现是浮点精度问题——sqrtl在大整数下取整可能偏差 1。后来改成“公式求根 整数修正”组合拳才彻底稳定。现在我更倾向于在 Python 里用isqrt加整数二分虽然代码长一点但心里踏实。还有一个心得是关于上界的。我第一次图省事直接设hi 1e18后来怀疑某些极端数据可能超过这个值干脆改成倍增扩张从此再没有为“上界该设多大”纠结过。这个技巧可以迁移到几乎所有二分答案题里强烈推荐。如果你也在刷这道题建议按这个顺序来先手算一遍我上面给的小样例理解k*(k1)/2的来源再自己写一版完整的二分代码最后用mountainHeight1、n1这类极端输入做验证。整个过程走下来你对二分答案和递增代价模型的理解会扎实很多。