看到 3296 这个题号刷题量够的朋友应该会条件反射地想到又是二分答案。作为周赛 430 里的一道中等题移山所需的最少秒数LeetCode 3296确实没有绕弯子外层二分时间内层贪心核算产能。它跟 073 爱吃香蕉的狒狒875. Koko Eating Bananas是同一个骨架只不过把每小时吃几根香蕉换成了每秒移多少土还加了一个越挖越累的边际成本递增设定难度一下就从中等偏易变成了中等偏上一点点。这篇文章直接拆模型、推公式、给三种语言的实现再把我自己踩过的坑和排查经验一并倒出来。适合正在系统刷二分答案这类题的同学也适合周赛前临时抱佛脚的人。只要你能理解为什么可以二分时间以及一个工人在 T 秒内最多能移多少单位剩下的一切都是体力活。1. 题目到底在说什么先建立直觉1.1 把移山翻译成数学模型题目给两个数组mountainHeight表示每座山的高度workerTimes表示每个工人的时间系数。关键设定是工人 i 每降低山体 1 个单位高度所花时间是递增的——第 1 个单位花workerTimes[i]秒第 2 个单位花2 * workerTimes[i]秒第 3 个单位花3 * workerTimes[i]秒以此类推。所以如果让工人 i 单独处理一座高度为 h 的山总耗时是workerTimes[i] * (1 2 ... h) workerTimes[i] * h * (h 1) / 2这不就是三角数嘛。题目问的是所有工人同时开工最少需要多少秒才能把所有山的高度全部降到 0。这里有一个很容易想歪的点工人能不能换山能。而且因为每单位土的工作量完全独立工人之间也不存在配合惩罚所以问题可以化简成在 T 秒内所有工人的总产能是否大于等于所有山的总高度。你不需要真的去模拟谁搬哪座山只需要算出每个工人 T 秒内最多能搬多少单位然后求和对比即可。这是整道题最重要的化简想通了后面就顺了。1.2 为什么一上来就要想到二分答案先想一个问题给定一个时间 T我能不能在有限时间内判断T 秒够不够如果能而且这个判断结果随着 T 增大是单调的那就可以二分。单调性非常明显如果 T 秒能搬完那 T 1 秒肯定也能搬完无非是多歇一秒。反过来如果 T 秒搬不完那更少的时间更搬不完。于是答案就在不可行和可行的边界上这天然就是二分搜索能处理的结构。二分答案的通用套路是猜一个答案 mid用一个 check(mid) 函数验证它是否可行然后根据结果缩小区间。这道题的 check 函数就是计算所有工人在 mid 秒内的总产能看是否不小于总高度。这个套路在力扣上出现频率极高你不需要什么高深技巧只需要记住凡是题目问最少多少时间 / 多少秒 / 多少天而且你能写出一个单调的可行性判定函数优先想二分答案就对了。1.3 和热门题 875 / 073 的同与不同为什么热词里总把这道题和 073 爱吃香蕉的狒狒 放在一起因为它们共享同一个骨架。073 是给定香蕉堆 piles猴子每小时吃 k 根求能在 h 小时内吃完的最小 k。check(K) 就是遍历每一堆算ceil(pile / K)求和判断是否小于等于 h。这里二分的变量是速度check 里是除法。3296 是给定山高和工人求搬完所有山的最少秒数。check(T) 是遍历每个工人算他在 T 秒内最多能搬多少单位求和判断是否大于等于总高度。这里二分的变量是时间check 里是解一个一元二次不等式。差别在哪里073 的产能是线性的速度越快吃得越快每小时产能固定是 K。3296 的产能是边际递减的工人搬第 1 单位很轻松搬第 10 单位的时候已经累得不行了。同样一个工人你不能直接拿T / workerTimes[i]去算产能因为每个单位的成本不一样。正是这个差别让题目的难度从中等偏下变成了中等。2. 核心数学工具一个工人 T 秒内最多能干多少活2.1 从越挖越累到三角数公式来仔细推一下单个工人的产能。假设工人 i 的时间系数是 w他连续工作 T 秒最多能搬多少个单位设他搬了 k 个单位。搬第 1 个单位需要 1 * w 秒搬第 2 个单位需要 2 * w 秒……搬第 k 个单位需要 k * w 秒总共需要w 2w 3w ... kw w * (1 2 ... k) w * k * (k 1) / 2所以要判断工人 i 在 T 秒内能不能搬 k 个单位只需要验证w * k * (k 1) / 2 T举个例子w 1 的工人搬 3 个单位需要 1 2 3 6 秒。你让他干 5 秒他只能搬 2 个单位第 1 个花 1 秒第 2 个花 2 秒总共 3 秒第 3 个还需要 3 秒凑不够。这些数字很小手算一遍就能把公式钉在脑子里后面写代码就不容易把边界搞错。2.2 解一元二次不等式求最大 k现在的问题是给定 w 和 T求最大的整数 k使得w * k * (k 1) / 2 T。先把不等式变形。两边同时乘以 2w * k * (k 1) 2T这里要注意一个细节因为k * (k 1)一定是整数所以这个不等式等价于k * (k 1) floor(2T / w)为什么可以放心地取 floor因为左边是整数一个整数小于等于一个实数等价于它小于等于这个实数的整数部分。这个结论看起来简单但很多人写代码的时候会在2 * T / w的除法上翻车尤其是 C 里整数除法截断方向搞错。记住先右移取整再和整数左边比较就完全避开了浮点误差。令limit (2 * T) / w问题变成求最大 k 满足k * (k 1) limit。最粗暴的办法是二分 k但还有一个更优雅的做法。因为k * (k 1)非常接近k^2 k所以 k 的近似值就是sqrt(limit)附近。用整数开方函数isqrt拿到floor(sqrt(limit))然后做最多一两次微调k isqrt(limit) while k * (k 1) limit: k - 1 while (k 1) * (k 2) limit: k 1为什么微调次数最多一两次因为k * (k 1)和k^2的差大约是 k而 k 在sqrt(limit)附近。从 isqrt 的结果出发k 和真实解最多差 1 到 2 个整数所以这两个 while 循环基本只是保险实际跑不到几次。用limit (2 * T) / w而不是直接用浮点sqrt(2*T/w)这是我在实战中踩过坑之后养成的习惯后面第 2.4 节会专门说。2.3 不用 sqrt 的兜底方案内层再二分如果你用的语言没有isqrt或者你不想记这个开方 微调的写法也可以对 k 做二分。每次验证if w * mid * (mid 1) / 2 T: # mid 可行尝试更大 else: # mid 不可行缩小内层二分的范围是[0, limit]因为当 k 超过 limit 时k * (k 1)必然大于 limit不可能满足条件。这个方案的坏处是每个工人多一个 log limit 的复杂度但好处是思路无脑、不怕溢出、不容易写错。在 C 里实测下来即使 n 和 m 都到 1e4 级别外层二分 60 次乘以内层 31 次再乘以工人数依然在可接受范围内。Python 里如果担心超时还是优先用 isqrt 方案。我的建议是比赛时用你最有把握的写法。如果对浮点开方不放心内层二分反而更稳。刷题是为了 AC不是为了炫技。2.4 为什么整数运算比浮点 sqrt 更稳这道题的数据范围决定了答案可能很大。假设mountainHeight每个元素到 1e5长度到 1e5那么总高度就是 1e10workerTimes里如果有 1e6 的时间系数答案直接奔着 1e16 去了。double只有 15 到 16 位有效数字。你在算sqrt(2 * T / w)的时候如果2*T/w是 1e15 级别浮点开方结果的误差可能跨越好几个整数。比如真实 k 是 44721359浮点算出来是 44721360你直接拿这个 k 去算产能就会比真实值多算一大截check 函数从不可行误判成可行二分结果直接 WA。整数开方isqrt是精确的它返回的就是floor(sqrt(n))不存在舍入误差。配合那最多一两次的微调循环得到的一定是精确的最大 k。所以在 Python 里我强烈推荐math.isqrt在 C 里如果对sqrtl的平台精度没把握就老老实实写整数二分开方或者用sqrtl之后再微调千万别裸用sqrt完事。3. 判定函数与二分框架的完整实现3.1 check(T) 的写法与剪枝check 函数的逻辑很直接给定时间 T遍历每个工人算出他在 T 秒内最多能搬多少单位累加起来最后判断总产能是否大于等于totalHeight。一个很实用的优化是提前退出一旦累加值已经大于等于totalHeight立刻返回 true不用再算后面的工人。这个优化在数据量大时效果显著尤其 Python 这种解释型语言能少算一个工人就少算一个。另一个优化是给workerTimes排序让时间系数小的工人产能大的排在前面。这样累加值会更快地达到目标提前退出的概率更高。排序本身 O(m log m)相对二分过程来说几乎可以忽略。当然这不是必须的但实测对运行时间有肉眼可见的改善。check 函数还有一个容易忽略的边界如果某个工人的 w 特别大导致limit (2 * T) / w为 0那么他的最大 k 就是 0说明他在 T 秒内连一个单位都搬不完。这是合法的不用特殊处理但你在推公式的时候要能意识到这种情况存在。3.2 二分边界怎么定下界、上界与倍增逼近下界很好定0。因为总高度大于 0 的时候0 秒肯定不可行所以答案一定大于 0。上界是很多人纠结的地方。最朴素的想法是让最快的工人一个人搬完全部山于是上界等于min(w) * totalHeight * (totalHeight 1) / 2。但这个式子有两个问题一是totalHeight * totalHeight可能溢出 64 位整数二是这个上界太粗糙会让二分的区间特别大白白多跑几十次。更稳妥的做法是倍增逼近从hi 1开始如果can(hi)为假就把hi翻倍直到某个hi可行。这个做法的好处是完全不用动脑子算上界而且最终hi和真实答案的差距不超过 2 倍二分次数不会浪费。缺点是你要写两个循环一个倍增找上界一个正常二分。但代码量也就多了三行。二分循环我用的是左闭右闭写法lo 0 hi 倍增得到的可行上界 while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 return lo这里lo始终是不可行的候选hi始终是可行的候选。循环结束时lo hi就是最小的可行时间。这个写法比左闭右开更直观不容易在 1/-1 上出错。3.3 三种语言的参考代码先给 Python 主版本这个版本用isqrt代码最短逻辑最清晰from math import isqrt from typing import List class Solution: def minimumSeconds(self, mountainHeight: List[int], workerTimes: List[int]) - int: total sum(mountainHeight) if total 0: return 0 workerTimes.sort() def can(T: int) - bool: s 0 for w in workerTimes: limit (2 * T) // w k isqrt(limit) while k * (k 1) limit: k - 1 while (k 1) * (k 2) limit: k 1 s k if s total: return True return False hi 1 while not can(hi): hi * 2 lo 0 while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 return loC 版本这里我用整数二分求 k的兜底写法主要是为了照顾那些不想碰浮点开方的朋友。如果你愿意用sqrtl加微调也可以替换注意把中间量全部用long longclass Solution { public: long long minimumSeconds(vectorint mountainHeight, vectorint workerTimes) { long long total 0; for (int h : mountainHeight) total h; if (total 0) return 0; sort(workerTimes.begin(), workerTimes.end()); auto can [](long long T) - bool { long long s 0; for (int w : workerTimes) { long long limit (2 * T) / w; long long k 0; long long l 0, r limit; while (l r) { long long mid (l r 1) / 2; if (mid * (mid 1) limit) l mid; else r mid - 1; } k l; s k; if (s total) return true; } return false; }; long long hi 1; while (!can(hi)) hi * 2; long long lo 0; while (lo hi) { long long mid (lo hi) / 2; if (can(mid)) hi mid; else lo mid 1; } return lo; } };Java 版本和 C 几乎一样把 lambda 改成普通方法二分求 k 的部分直接复用即可。这里我就不贴完整代码了核心就一行求最大 k 满足k * (k 1) limit。三种语言殊途同归关键是理解 check 函数里的数学。4. 复杂度、优化与细节陷阱4.1 时间复杂度与空间复杂度外层二分加倍增上界总的迭代次数大约是O(log(answer) log(answer))也就是 O(log A)其中 A 是答案量级。每次 check 要遍历 m 个工人用 isqrt 方案每个工人 O(1) 微调总复杂度 O(m log A)。用内层二分求 k 的方案每个工人 O(log limit)总复杂度 O(m log A log A)。空间复杂度是 O(1)只用了几个变量。排序 workerTimes 需要 O(log m) 的栈空间如果算排序的话但通常可以忽略。实际跑下来Python 版用 isqrt 方案在 n、m 都是 1e4 到 1e5 级别的数据上单测也就是几十毫秒到一两百毫秒。内层二分方案在 C 里也完全够用但 Python 里建议别这么写会明显慢一截。4.2 容易被忽略的边界与溢出第一个边界总高度为 0。如果所有山的高度本来就是 0答案直接是 0连二分都不用跑。这个特判不写你的can(0)会因为total 0而误判为可行二分也能跑出 0但会白白做很多无意义的计算。我习惯在一开始就把它写掉。第二个边界C 里的溢出。注意mid * (mid 1)这个乘法mid 最大到 limitlimit 最大是2 * T / w。T 如果到 1e16limit 可能到 2e16mid * (mid 1)直接爆 64 位不会因为 mid * (mid1) 最多也就是 limit 左右limit 是 2e16远小于 9.2e18 的 long long 上限。真正要小心的是2 * T本身T 到 1e162*T 是 2e16没问题。但如果你写的是int那 T 到 1e9 就爆了所以务必用 long long。Python 用户没有这个烦恼但你在读 C 题解的时候要知道这个点。第三个边界limit为 0。当 T 很小且 w 很大时(2 * T) / w为 0此时最大 k 是 0这个工人没有任何产能。代码里的两个 while 循环要能正确处理 k 0 的情况别让(k1)*(k2)在下标上出事——它不涉及数组下标所以其实没事但逻辑上要理解。4.3 验证用的手算用例拿几个小例子在脑子里跑一遍能帮你确认公式没写错。例 1mountainHeight [1, 2]workerTimes [1, 1]。总高度 3两个工人系数都是 1。T 2每个工人limit 4 / 1 4最大 k 满足k(k1) 4k 1因为 122 4236 4。总产能 2 3不可行。T 3每个工人limit 6k 22*36 6。总产能 4 3可行。所以答案是 3。手动模拟一下工人 A 花 1 秒搬完高度 1 的山工人 B 在高度 2 的山上先花 1 秒搬掉第一层再花 2 秒搬掉第二层总共 3 秒。2 秒确实不够因为高度 2 的山至少需要 3 秒才能清空。例 2mountainHeight [0, 0]workerTimes [5, 7]。总高度 0直接返回 0。例 3mountainHeight [3]workerTimes [2]。一个工人系数 2要搬 3 个单位耗时2 * (1 2 3) 12。check 里验证T 11 时limit 22 / 2 11最大 k 满足k(k1) 11k 33*412 11所以 k 2产能 2 3不可行。T 12 时limit 24 / 2 12k 3产能 3可行。答案 12完美吻合公式。例 4mountainHeight [100000000]workerTimes [1]。单个工人搬 1e8 单位。需要找最小 k 使k(k1)/2 1e8。k 14142 时14142 * 14143 / 2 100005153所以答案就是 100005153。这个例子能检验你的二分上界够不够大——答案在 1e8 级别如果你的 hi 从 1 倍增大概 27 次就到 1.34e8 了没问题。5. 实测记录与常见问题排查5.1 我踩过的三个坑第一个坑直接用浮点 sqrt 求 k。我第一次写这题的时候图省事写了int k sqrt(2.0 * T / w)然后直接拿去累加结果在几个大数据上 WA。排查半天发现是浮点舍入导致 k 比真实值大 1产能被高估check 误判。后来改成浮点近似 整数微调才通过。如果你不想经历这个排查过程直接上 isqrt 或整数二分。第二个坑二分上界定死导致漏答案。我一开始想用min(w) * total * (total 1) / 2作为 hi结果在构造极限数据时发现 total 是 1e10平方直接超出 long long 的舒适区虽然最终没溢出到负数但编译器在做乘法时已经产生了错误的中间值。换成倍增逼近之后再也没纠结过上界。第三个坑Python 里没做提前退出。第一次提交的 check 函数是老老实实把所有工人算完再比较的版本在 m 很大的时候出现 TLE。加了if s total: return True之后运行时间直接降了一个量级。别小看这一行二分答案的 check 调用次数往往是几十上百次每次少算一半工人总时间就完全不同了。5.2 常见问题速查表症状原因解决方案样例能过大数据 WAcheck 里 k 计算不准浮点开方误差改用 isqrt 或整数二分加微调循环答案偏大或偏小且不稳定二分边界写错lo/hi 更新逻辑混乱用左闭右闭模板保证 lo 不可行、hi 可行运行超时check 里没有提前退出或内层二分过重加提前退出排序让大产能工人先算编译报错或负数结果C 里用了 int乘法溢出全部中间量用 long longT 用 long longtotal 为 0 时行为异常没有特判函数开头加if total 0: return 0单个工人案例算不对三角数公式记错手推 12...k验证 w1、3 单位耗时 6 秒5.3 周赛 430 现场的观察这道题在周赛 430 现场的实际体验是卡住大多数人的点其实不是二分而是每个工人的产能怎么求。很多朋友看到移山就慌了或者下意识地套 Koko 的T / w线性公式结果 check 函数从一开始就是错的。所以如果你在场上 20 分钟没思路不妨回头看看题干里那句时间递增的设定它才是整道题的题眼。这种找边际成本规律 二分答案的组合拳在力扣里并不是孤例。2517 礼盒的最大甜蜜度、2594 修车的最少时间、2226 每个孩子最多能分到多少糖果都是同类套路二分答案 贪心或数学 check。你把这题吃透等于顺手给这一整类题都做了预习。尤其是 2594修车师傅修第 n 辆车耗时rank[i] * n^2check 里要对每个师傅解一个二次不等式和本题的思路几乎一模一样强烈建议连着做一遍。最后再分享一个我自己的习惯拿到最小时间类题目先别急着动二分先把 check 函数写出来。check 里的数学想清楚了二分框架只是体力活如果 check 没想清楚就套模板WA 了都不知道是边界问题还是模型问题。另外一个小技巧不管题目数据范围多大先写if total 0: return 0这个特判它能让你的二分下界干干净净省掉一大堆无所谓的边界讨论。这个题后续如果要扩展把三角成本换成平方成本、指数成本check 里的求根公式跟着换就行骨架永远不变。
看到 3296 这个题号刷题量够的朋友应该会条件反射地想到又是二分答案。作为周赛 430 里的一道中等题移山所需的最少秒数LeetCode 3296确实没有绕弯子外层二分时间内层贪心核算产能。它跟 073 爱吃香蕉的狒狒875. Koko Eating Bananas是同一个骨架只不过把每小时吃几根香蕉换成了每秒移多少土还加了一个越挖越累的边际成本递增设定难度一下就从中等偏易变成了中等偏上一点点。这篇文章直接拆模型、推公式、给三种语言的实现再把我自己踩过的坑和排查经验一并倒出来。适合正在系统刷二分答案这类题的同学也适合周赛前临时抱佛脚的人。只要你能理解为什么可以二分时间以及一个工人在 T 秒内最多能移多少单位剩下的一切都是体力活。1. 题目到底在说什么先建立直觉1.1 把移山翻译成数学模型题目给两个数组mountainHeight表示每座山的高度workerTimes表示每个工人的时间系数。关键设定是工人 i 每降低山体 1 个单位高度所花时间是递增的——第 1 个单位花workerTimes[i]秒第 2 个单位花2 * workerTimes[i]秒第 3 个单位花3 * workerTimes[i]秒以此类推。所以如果让工人 i 单独处理一座高度为 h 的山总耗时是workerTimes[i] * (1 2 ... h) workerTimes[i] * h * (h 1) / 2这不就是三角数嘛。题目问的是所有工人同时开工最少需要多少秒才能把所有山的高度全部降到 0。这里有一个很容易想歪的点工人能不能换山能。而且因为每单位土的工作量完全独立工人之间也不存在配合惩罚所以问题可以化简成在 T 秒内所有工人的总产能是否大于等于所有山的总高度。你不需要真的去模拟谁搬哪座山只需要算出每个工人 T 秒内最多能搬多少单位然后求和对比即可。这是整道题最重要的化简想通了后面就顺了。1.2 为什么一上来就要想到二分答案先想一个问题给定一个时间 T我能不能在有限时间内判断T 秒够不够如果能而且这个判断结果随着 T 增大是单调的那就可以二分。单调性非常明显如果 T 秒能搬完那 T 1 秒肯定也能搬完无非是多歇一秒。反过来如果 T 秒搬不完那更少的时间更搬不完。于是答案就在不可行和可行的边界上这天然就是二分搜索能处理的结构。二分答案的通用套路是猜一个答案 mid用一个 check(mid) 函数验证它是否可行然后根据结果缩小区间。这道题的 check 函数就是计算所有工人在 mid 秒内的总产能看是否不小于总高度。这个套路在力扣上出现频率极高你不需要什么高深技巧只需要记住凡是题目问最少多少时间 / 多少秒 / 多少天而且你能写出一个单调的可行性判定函数优先想二分答案就对了。1.3 和热门题 875 / 073 的同与不同为什么热词里总把这道题和 073 爱吃香蕉的狒狒 放在一起因为它们共享同一个骨架。073 是给定香蕉堆 piles猴子每小时吃 k 根求能在 h 小时内吃完的最小 k。check(K) 就是遍历每一堆算ceil(pile / K)求和判断是否小于等于 h。这里二分的变量是速度check 里是除法。3296 是给定山高和工人求搬完所有山的最少秒数。check(T) 是遍历每个工人算他在 T 秒内最多能搬多少单位求和判断是否大于等于总高度。这里二分的变量是时间check 里是解一个一元二次不等式。差别在哪里073 的产能是线性的速度越快吃得越快每小时产能固定是 K。3296 的产能是边际递减的工人搬第 1 单位很轻松搬第 10 单位的时候已经累得不行了。同样一个工人你不能直接拿T / workerTimes[i]去算产能因为每个单位的成本不一样。正是这个差别让题目的难度从中等偏下变成了中等。2. 核心数学工具一个工人 T 秒内最多能干多少活2.1 从越挖越累到三角数公式来仔细推一下单个工人的产能。假设工人 i 的时间系数是 w他连续工作 T 秒最多能搬多少个单位设他搬了 k 个单位。搬第 1 个单位需要 1 * w 秒搬第 2 个单位需要 2 * w 秒……搬第 k 个单位需要 k * w 秒总共需要w 2w 3w ... kw w * (1 2 ... k) w * k * (k 1) / 2所以要判断工人 i 在 T 秒内能不能搬 k 个单位只需要验证w * k * (k 1) / 2 T举个例子w 1 的工人搬 3 个单位需要 1 2 3 6 秒。你让他干 5 秒他只能搬 2 个单位第 1 个花 1 秒第 2 个花 2 秒总共 3 秒第 3 个还需要 3 秒凑不够。这些数字很小手算一遍就能把公式钉在脑子里后面写代码就不容易把边界搞错。2.2 解一元二次不等式求最大 k现在的问题是给定 w 和 T求最大的整数 k使得w * k * (k 1) / 2 T。先把不等式变形。两边同时乘以 2w * k * (k 1) 2T这里要注意一个细节因为k * (k 1)一定是整数所以这个不等式等价于k * (k 1) floor(2T / w)为什么可以放心地取 floor因为左边是整数一个整数小于等于一个实数等价于它小于等于这个实数的整数部分。这个结论看起来简单但很多人写代码的时候会在2 * T / w的除法上翻车尤其是 C 里整数除法截断方向搞错。记住先右移取整再和整数左边比较就完全避开了浮点误差。令limit (2 * T) / w问题变成求最大 k 满足k * (k 1) limit。最粗暴的办法是二分 k但还有一个更优雅的做法。因为k * (k 1)非常接近k^2 k所以 k 的近似值就是sqrt(limit)附近。用整数开方函数isqrt拿到floor(sqrt(limit))然后做最多一两次微调k isqrt(limit) while k * (k 1) limit: k - 1 while (k 1) * (k 2) limit: k 1为什么微调次数最多一两次因为k * (k 1)和k^2的差大约是 k而 k 在sqrt(limit)附近。从 isqrt 的结果出发k 和真实解最多差 1 到 2 个整数所以这两个 while 循环基本只是保险实际跑不到几次。用limit (2 * T) / w而不是直接用浮点sqrt(2*T/w)这是我在实战中踩过坑之后养成的习惯后面第 2.4 节会专门说。2.3 不用 sqrt 的兜底方案内层再二分如果你用的语言没有isqrt或者你不想记这个开方 微调的写法也可以对 k 做二分。每次验证if w * mid * (mid 1) / 2 T: # mid 可行尝试更大 else: # mid 不可行缩小内层二分的范围是[0, limit]因为当 k 超过 limit 时k * (k 1)必然大于 limit不可能满足条件。这个方案的坏处是每个工人多一个 log limit 的复杂度但好处是思路无脑、不怕溢出、不容易写错。在 C 里实测下来即使 n 和 m 都到 1e4 级别外层二分 60 次乘以内层 31 次再乘以工人数依然在可接受范围内。Python 里如果担心超时还是优先用 isqrt 方案。我的建议是比赛时用你最有把握的写法。如果对浮点开方不放心内层二分反而更稳。刷题是为了 AC不是为了炫技。2.4 为什么整数运算比浮点 sqrt 更稳这道题的数据范围决定了答案可能很大。假设mountainHeight每个元素到 1e5长度到 1e5那么总高度就是 1e10workerTimes里如果有 1e6 的时间系数答案直接奔着 1e16 去了。double只有 15 到 16 位有效数字。你在算sqrt(2 * T / w)的时候如果2*T/w是 1e15 级别浮点开方结果的误差可能跨越好几个整数。比如真实 k 是 44721359浮点算出来是 44721360你直接拿这个 k 去算产能就会比真实值多算一大截check 函数从不可行误判成可行二分结果直接 WA。整数开方isqrt是精确的它返回的就是floor(sqrt(n))不存在舍入误差。配合那最多一两次的微调循环得到的一定是精确的最大 k。所以在 Python 里我强烈推荐math.isqrt在 C 里如果对sqrtl的平台精度没把握就老老实实写整数二分开方或者用sqrtl之后再微调千万别裸用sqrt完事。3. 判定函数与二分框架的完整实现3.1 check(T) 的写法与剪枝check 函数的逻辑很直接给定时间 T遍历每个工人算出他在 T 秒内最多能搬多少单位累加起来最后判断总产能是否大于等于totalHeight。一个很实用的优化是提前退出一旦累加值已经大于等于totalHeight立刻返回 true不用再算后面的工人。这个优化在数据量大时效果显著尤其 Python 这种解释型语言能少算一个工人就少算一个。另一个优化是给workerTimes排序让时间系数小的工人产能大的排在前面。这样累加值会更快地达到目标提前退出的概率更高。排序本身 O(m log m)相对二分过程来说几乎可以忽略。当然这不是必须的但实测对运行时间有肉眼可见的改善。check 函数还有一个容易忽略的边界如果某个工人的 w 特别大导致limit (2 * T) / w为 0那么他的最大 k 就是 0说明他在 T 秒内连一个单位都搬不完。这是合法的不用特殊处理但你在推公式的时候要能意识到这种情况存在。3.2 二分边界怎么定下界、上界与倍增逼近下界很好定0。因为总高度大于 0 的时候0 秒肯定不可行所以答案一定大于 0。上界是很多人纠结的地方。最朴素的想法是让最快的工人一个人搬完全部山于是上界等于min(w) * totalHeight * (totalHeight 1) / 2。但这个式子有两个问题一是totalHeight * totalHeight可能溢出 64 位整数二是这个上界太粗糙会让二分的区间特别大白白多跑几十次。更稳妥的做法是倍增逼近从hi 1开始如果can(hi)为假就把hi翻倍直到某个hi可行。这个做法的好处是完全不用动脑子算上界而且最终hi和真实答案的差距不超过 2 倍二分次数不会浪费。缺点是你要写两个循环一个倍增找上界一个正常二分。但代码量也就多了三行。二分循环我用的是左闭右闭写法lo 0 hi 倍增得到的可行上界 while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 return lo这里lo始终是不可行的候选hi始终是可行的候选。循环结束时lo hi就是最小的可行时间。这个写法比左闭右开更直观不容易在 1/-1 上出错。3.3 三种语言的参考代码先给 Python 主版本这个版本用isqrt代码最短逻辑最清晰from math import isqrt from typing import List class Solution: def minimumSeconds(self, mountainHeight: List[int], workerTimes: List[int]) - int: total sum(mountainHeight) if total 0: return 0 workerTimes.sort() def can(T: int) - bool: s 0 for w in workerTimes: limit (2 * T) // w k isqrt(limit) while k * (k 1) limit: k - 1 while (k 1) * (k 2) limit: k 1 s k if s total: return True return False hi 1 while not can(hi): hi * 2 lo 0 while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 return loC 版本这里我用整数二分求 k的兜底写法主要是为了照顾那些不想碰浮点开方的朋友。如果你愿意用sqrtl加微调也可以替换注意把中间量全部用long longclass Solution { public: long long minimumSeconds(vectorint mountainHeight, vectorint workerTimes) { long long total 0; for (int h : mountainHeight) total h; if (total 0) return 0; sort(workerTimes.begin(), workerTimes.end()); auto can [](long long T) - bool { long long s 0; for (int w : workerTimes) { long long limit (2 * T) / w; long long k 0; long long l 0, r limit; while (l r) { long long mid (l r 1) / 2; if (mid * (mid 1) limit) l mid; else r mid - 1; } k l; s k; if (s total) return true; } return false; }; long long hi 1; while (!can(hi)) hi * 2; long long lo 0; while (lo hi) { long long mid (lo hi) / 2; if (can(mid)) hi mid; else lo mid 1; } return lo; } };Java 版本和 C 几乎一样把 lambda 改成普通方法二分求 k 的部分直接复用即可。这里我就不贴完整代码了核心就一行求最大 k 满足k * (k 1) limit。三种语言殊途同归关键是理解 check 函数里的数学。4. 复杂度、优化与细节陷阱4.1 时间复杂度与空间复杂度外层二分加倍增上界总的迭代次数大约是O(log(answer) log(answer))也就是 O(log A)其中 A 是答案量级。每次 check 要遍历 m 个工人用 isqrt 方案每个工人 O(1) 微调总复杂度 O(m log A)。用内层二分求 k 的方案每个工人 O(log limit)总复杂度 O(m log A log A)。空间复杂度是 O(1)只用了几个变量。排序 workerTimes 需要 O(log m) 的栈空间如果算排序的话但通常可以忽略。实际跑下来Python 版用 isqrt 方案在 n、m 都是 1e4 到 1e5 级别的数据上单测也就是几十毫秒到一两百毫秒。内层二分方案在 C 里也完全够用但 Python 里建议别这么写会明显慢一截。4.2 容易被忽略的边界与溢出第一个边界总高度为 0。如果所有山的高度本来就是 0答案直接是 0连二分都不用跑。这个特判不写你的can(0)会因为total 0而误判为可行二分也能跑出 0但会白白做很多无意义的计算。我习惯在一开始就把它写掉。第二个边界C 里的溢出。注意mid * (mid 1)这个乘法mid 最大到 limitlimit 最大是2 * T / w。T 如果到 1e16limit 可能到 2e16mid * (mid 1)直接爆 64 位不会因为 mid * (mid1) 最多也就是 limit 左右limit 是 2e16远小于 9.2e18 的 long long 上限。真正要小心的是2 * T本身T 到 1e162*T 是 2e16没问题。但如果你写的是int那 T 到 1e9 就爆了所以务必用 long long。Python 用户没有这个烦恼但你在读 C 题解的时候要知道这个点。第三个边界limit为 0。当 T 很小且 w 很大时(2 * T) / w为 0此时最大 k 是 0这个工人没有任何产能。代码里的两个 while 循环要能正确处理 k 0 的情况别让(k1)*(k2)在下标上出事——它不涉及数组下标所以其实没事但逻辑上要理解。4.3 验证用的手算用例拿几个小例子在脑子里跑一遍能帮你确认公式没写错。例 1mountainHeight [1, 2]workerTimes [1, 1]。总高度 3两个工人系数都是 1。T 2每个工人limit 4 / 1 4最大 k 满足k(k1) 4k 1因为 122 4236 4。总产能 2 3不可行。T 3每个工人limit 6k 22*36 6。总产能 4 3可行。所以答案是 3。手动模拟一下工人 A 花 1 秒搬完高度 1 的山工人 B 在高度 2 的山上先花 1 秒搬掉第一层再花 2 秒搬掉第二层总共 3 秒。2 秒确实不够因为高度 2 的山至少需要 3 秒才能清空。例 2mountainHeight [0, 0]workerTimes [5, 7]。总高度 0直接返回 0。例 3mountainHeight [3]workerTimes [2]。一个工人系数 2要搬 3 个单位耗时2 * (1 2 3) 12。check 里验证T 11 时limit 22 / 2 11最大 k 满足k(k1) 11k 33*412 11所以 k 2产能 2 3不可行。T 12 时limit 24 / 2 12k 3产能 3可行。答案 12完美吻合公式。例 4mountainHeight [100000000]workerTimes [1]。单个工人搬 1e8 单位。需要找最小 k 使k(k1)/2 1e8。k 14142 时14142 * 14143 / 2 100005153所以答案就是 100005153。这个例子能检验你的二分上界够不够大——答案在 1e8 级别如果你的 hi 从 1 倍增大概 27 次就到 1.34e8 了没问题。5. 实测记录与常见问题排查5.1 我踩过的三个坑第一个坑直接用浮点 sqrt 求 k。我第一次写这题的时候图省事写了int k sqrt(2.0 * T / w)然后直接拿去累加结果在几个大数据上 WA。排查半天发现是浮点舍入导致 k 比真实值大 1产能被高估check 误判。后来改成浮点近似 整数微调才通过。如果你不想经历这个排查过程直接上 isqrt 或整数二分。第二个坑二分上界定死导致漏答案。我一开始想用min(w) * total * (total 1) / 2作为 hi结果在构造极限数据时发现 total 是 1e10平方直接超出 long long 的舒适区虽然最终没溢出到负数但编译器在做乘法时已经产生了错误的中间值。换成倍增逼近之后再也没纠结过上界。第三个坑Python 里没做提前退出。第一次提交的 check 函数是老老实实把所有工人算完再比较的版本在 m 很大的时候出现 TLE。加了if s total: return True之后运行时间直接降了一个量级。别小看这一行二分答案的 check 调用次数往往是几十上百次每次少算一半工人总时间就完全不同了。5.2 常见问题速查表症状原因解决方案样例能过大数据 WAcheck 里 k 计算不准浮点开方误差改用 isqrt 或整数二分加微调循环答案偏大或偏小且不稳定二分边界写错lo/hi 更新逻辑混乱用左闭右闭模板保证 lo 不可行、hi 可行运行超时check 里没有提前退出或内层二分过重加提前退出排序让大产能工人先算编译报错或负数结果C 里用了 int乘法溢出全部中间量用 long longT 用 long longtotal 为 0 时行为异常没有特判函数开头加if total 0: return 0单个工人案例算不对三角数公式记错手推 12...k验证 w1、3 单位耗时 6 秒5.3 周赛 430 现场的观察这道题在周赛 430 现场的实际体验是卡住大多数人的点其实不是二分而是每个工人的产能怎么求。很多朋友看到移山就慌了或者下意识地套 Koko 的T / w线性公式结果 check 函数从一开始就是错的。所以如果你在场上 20 分钟没思路不妨回头看看题干里那句时间递增的设定它才是整道题的题眼。这种找边际成本规律 二分答案的组合拳在力扣里并不是孤例。2517 礼盒的最大甜蜜度、2594 修车的最少时间、2226 每个孩子最多能分到多少糖果都是同类套路二分答案 贪心或数学 check。你把这题吃透等于顺手给这一整类题都做了预习。尤其是 2594修车师傅修第 n 辆车耗时rank[i] * n^2check 里要对每个师傅解一个二次不等式和本题的思路几乎一模一样强烈建议连着做一遍。最后再分享一个我自己的习惯拿到最小时间类题目先别急着动二分先把 check 函数写出来。check 里的数学想清楚了二分框架只是体力活如果 check 没想清楚就套模板WA 了都不知道是边界问题还是模型问题。另外一个小技巧不管题目数据范围多大先写if total 0: return 0这个特判它能让你的二分下界干干净净省掉一大堆无所谓的边界讨论。这个题后续如果要扩展把三角成本换成平方成本、指数成本check 里的求根公式跟着换就行骨架永远不变。
