LeetCode 3296 题，“移山所需的最少秒数”，是第 430 场周赛的一道中等题。我第一次看到标题就隐约感觉到，这道题想考的不是“搬山”，而是二分答案。题干写得挺有迷惑性：一座山、好多个工人、每人按自己速度干活，而且越干越慢。如果你刷过 LeetCode 073 爱吃香蕉的狒狒，也就是那道经典的 Koko Eating Bananas，你马上能闻到熟悉的味道：给定一个时间上限，判断能不能完成，能就压缩时间，不能就放宽时间。这篇题解不打算只贴代码，而是从题意翻译、判定函数推导、完整实现到常见坑点，把 3296 从头到尾拆给你看。适合刚开始刷二分答案专题、周赛被卡过、或者想弄懂“为什么这样二分”的读者。
1. 先把题意读懂：不是“分配任务”，是“分配时间”
1.1 这道题到底在算什么
LeetCode 3296 的大意是：有一座山，初始高度为mountainHeight。有n个工人，第i个工人把山降低 1 单位本来需要workerTimes[i]秒，但他不是一直按固定速度干，而是越干越累，每多干一个单位，需要的时间按workerTimes[i]、2 * workerTimes[i]、3 * workerTimes[i]这样递增。换句话说，第i个工人连续第k次降低 1 米，这一米要花workerTimes[i] * k秒。所有工人可以同时开工，目标是让山的高度归零，问最少需要几秒。
这个计费方式听起来很怪，但生活里到处都是。比如爬 100 层楼，第一层用 1 分钟，第二层因为腿酸要用 2 分钟，第三层 3 分钟，越爬越慢。再比如某些平台上打车，里程越长，后面的每公里计价可能边际递增。关键点是：一个工人并不是“每秒固定产出固定单位”，他干得越多，后面每一米的边际时间越大。
如果工人i一共降了x米，他花的总时间就是：
workerTimes[i] * (1 + 2 + ... + x) = workerTimes[i] * x * (x + 1) / 2所以这不是一个普通线性分配问题，它带累进成本。很多人的第一反应是“谁快谁多干”，可惜快慢本身会随着分配量变化。直接贪心分配工作量非常麻烦，因为每个工人的“单位成本”不是一个常数。这也是这题能被评为中等难度的重要原因：一眼看不出来该用什么模型。
1.2 关键转折：先假设一个时间，再看能不能完成
感到麻烦，是因为我们试图直接回答“每个工人该分多少米”。但这类题的通用解法是调转方向：先猜一个总时间T，然后问“如果每个工人都有T秒可用，他们合计最多能干掉多少米？”如果合计干掉的高度大于等于目标mountainHeight，说明T是一个可行时间；否则就不可行。
这就是二分答案。为什么敢二分？因为可行性关于T是单调的：如果T秒能干完，那T + 1秒肯定也能干完；如果T秒干不完，那T - 1秒更干不完。于是所有可能的T可以看成一条从 false 到 true 的序列，我们要找的只是第一个 true 的位置。
这里的核心思想很容易被忽略：我们把一个“找最小耗时”的最优化问题，变成了一个“给定时间判可行性”的判定问题。判定问题比构造最优分配简单得多，因为它不需要告诉我们每个人到底干几米，只需要回答“够不够”。这种“反向思考”在算法题里非常常见，一旦想通，代码反而只是一层薄薄的二分壳。
1.3 从 Koko 到移山：二分答案的同一模型
刷题量上来之后你会发现，二分答案在很多题里都是一个壳，里面的 check 函数才是灵魂。LeetCode 073 爱吃香蕉的狒狒是给一个速度k，判断k小时内能不能吃完所有香蕉；LeetCode 2187 是给总时间totalTrips，判断每辆车在这段时间里能跑多少趟；LeetCode 2226 是给糖果数量，判断每人分x颗行不行。3296 在这条线上的位置，是把“单个工人能完成多少”变成一个带累进成本的计算。
这些题的共同点有三个：搜索空间是答案本身，而不是数组下标；check 是“独立计算每个个体产出，再汇总判断”；汇总判断只需要满足大于等于目标，不需要关心具体分配。记住这个模板，以后遇到任何奇怪计费方式，都能快速建模。3296 比 Koko 多绕的一步，是每个工人的产出公式需要解一个一元二次不等式，这就引出了下一节的内容。
2. 判定函数推导：一个工人 t 秒能挖多少米？
2.1 工作量与时间的关系式
假设当前尝试的总时间是T，对第i个工人，设他在T秒内最多能降低x米。由前面的公式，需要满足：
workerTimes[i] * (1 + 2 + ... + x) <= T整理一下：
workerTimes[i] * x * (x + 1) / 2 <= T这个不等式里有乘法、除法，直接暴力枚举x显然不行。但它是关于x的二次函数，所以可以解方程。为了推导方便，令w = workerTimes[i]，条件等价于：
x^2 + x - 2T / w <= 0这个二次不等式的正根在：
x = (sqrt(1 + 8T / w) - 1) / 2这个值不一定是整数，而我们要求的是满足条件的最大整数x。所以应该向下取整，再结合实际情况做一点修正。真正写代码时必做的操作是：算出浮点近似值后，在附近做一次 ±1 甚至 ±2 的校验。
2.2 浮点近似与 ±1 修正
直接用sqrt是有一个经典埋伏的。sqrt返回浮点数，浮点数本身有精度误差。极限情况下，理论结果是一个整数，但浮点数算出来可能是9999.9999999之类，直接取整会差 1。更稳妥的办法是把浮点结果作为起点，然后分别检查x、x + 1、x + 2，更新成实际最大的可行值。
举个例子：w = 1，T = 3。公式根为(sqrt(1 + 24) - 1) / 2 = (5 - 1) / 2 = 2，所以x = 2，校验1 * 2 * 3 / 2 = 3 <= 3，通过。再看w = 2，T = 5：根约为(sqrt(1 + 20) - 1) / 2 ≈ 1.79，向下取整是 1，校验x = 1时2 * 1 * 2 / 2 = 2 <= 5；x = 2时2 * 2 * 3 / 2 = 6 > 5，所以最大确实是 1。这个例子也说明，看到浮点是 1.79，不能四舍五入成 2，必须向下取整。
修正循环建议写成：
long long x = (long long)((sqrt(1 + 8.0 * T / w) - 1) / 2); while (w * (x + 1) * (x + 2) / 2 <= T) ++x; while (w * x * (x + 1) / 2 > T) --x;两个 while 最多跑几次，常数几乎可以忽略。有人担心会死循环：不会，因为第一个 while 只在条件满足时增加 x，第二个 while 只在条件不满足时减少 x，两个方向相反，最终一定会稳定。这种“近似 + 校正”的写法，比纯浮点数取整安全得多。
2.3 二分的上下界与数据类型
二分前要确定搜索区间。最简单可靠的上界是让最快的工人独自把整座山挖完：
hi = min(workerTimes) * mountainHeight * (mountainHeight + 1) / 2这个值一定可行，因为把全部工作交给一个工人，本就是问题允许的方案之一。最优化答案只会小于等于这个值。另一个常见做法是：
hi = 1; while (!check(hi)) hi *= 2;用倍增试探到一个可行上界。两种都可以，我实际写题更喜欢后者，因为省得自己算乘法上界，还天然适应各种修改后的数据范围。
在 LeetCode 3296 的数据范围下，答案很容易超过 10^10，因此二分的mid、check 里的总耗时都必须用 64 位整数，C++ 用long long，Java 用long。真正危险的是计算w * (x + 1) * (x + 2) / 2时中间乘积可能较大。题目约束下 long long 基本够用，但如果你在写自己的题解库，想覆盖更泛化的场景，可以在乘法那一步用__int128，或者把乘法拆开，降低中间值大小。
3. 完整代码与实现细节
3.1 C++17 示例与逐行解释
现在把上面思路变成可以直接跑的代码。我会在代码里注释每一步在干什么，方便复盘。
class Solution { public: long long minimumSeconds(int mountainHeight, vector<int>& workerTimes) { // 判定函数：给定 totalSeconds，能不能把山移平？ auto ok = [&](long long totalSeconds) -> bool { long long sum = 0; for (long long w : workerTimes) { // 当前工人在 totalSeconds 内最多能挖多少米 long long x = (long long)((sqrt(1 + 8.0 * totalSeconds / w) - 1) / 2); while (w * (x + 1) * (x + 2) / 2 <= totalSeconds) ++x; while (w * x * (x + 1) / 2 > totalSeconds) --x; sum += x; if (sum >= mountainHeight) return true; // 提前退出，不用算完 } return false; }; // 二分上界：倍增到一个可行时间 long long lo = 0, hi = 1; while (!ok(hi)) hi *= 2; // 标准二分：找最小可行时间 while (lo < hi) { long long mid = (lo + hi) / 2; if (ok(mid)) hi = mid; else lo = mid + 1; } return lo; } };几个细节值得说。sum += x; if (sum >= mountainHeight) return true;这个提前返回，是因为判定函数只关心“够不够”，不用把每个工人都算完。除非数据极端，否则这个提前返回能在二分的早期阶段省下不少时间。sqrt(1 + 8.0 * totalSeconds / w)里，我把totalSeconds写在8.0旁边，先把整数转成浮点，避免整数除法直接变成 0。浮点只用来给一个初始近似值，真正保证正确的是后面两个 while。
3.2 Python 参考写法
Python 版实现起来更随意，因为 Python 的整数没有溢出概念，乘法随便写。
import math from typing import List class Solution: def minimumSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int: def ok(total: int) -> bool: done = 0 for w in workerTimes: x = int((math.sqrt(1 + 8 * total / w) - 1) / 2) while w * (x + 1) * (x + 2) // 2 <= total: x += 1 while w * x * (x + 1) // 2 > total: x -= 1 done += x if done >= mountainHeight: return True return False lo, hi = 0, 1 while not ok(hi): hi *= 2 while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return loPython 里int(...)是向零取整，对正数和向下取整效果一样。8 * total / w会先做浮点除法，不会截断，所以近似值可以放心用。修正循环的写法与 C++ 完全一致，逻辑也一模一样。
3.3 手动验证几个典型样例
拿一个简单样例验证：mountainHeight = 3，workerTimes = [1, 2]。试T = 2，工人 0 最多降 1 米，因为降 2 米要1 + 2 = 3秒；工人 1 最多降 1 米，因为降 1 米要 2 秒，降 2 米要 6 秒。合计是 2，不够 3，所以 2 秒不行。再试T = 3，工人 0 能降 2 米，用时 3 秒；工人 1 能降 1 米，用时 2 秒；合计 3，正好够。答案就是 3。
再看一个最简单的情况：mountainHeight = 1，workerTimes = [5]，答案显然是 5。代码里ok(0)为 false，二分最终会让lo和hi收敛到 5。如果mountainHeight = 4，workerTimes = [1, 1, 1]，T = 2时每个工人最多降 1 米，三人合计 3，不够；T = 3时每个工人最多降 2 米，三人合计 6，够了。答案是 3，不是 4，因为三个人都并行工作，第 3 秒已经能创造出 6 米的总降低量。
4. 踩坑记：从 0 到 AC 最常见的五个坑
4.1 二分边界写错，直接死循环
二分答案最常见的错误不是 check 写错，而是边界更新写错。有些人把lo初始化为 1，hi初始化得很大，然后写while (lo < hi)，里面mid = lo + (hi - lo) / 2，可行时lo = mid，结果在hi - lo = 1时卡死。要避免这个问题，关键是想清楚lo和hi各自的含义。
我习惯让lo始终是“不可行时间”，hi始终是“可行时间”。所以当ok(mid)为 true 时，答案不可能大于等于mid，右边界收缩到mid；当ok(mid)为 false 时，答案不可能小于等于mid，左边界推进到mid + 1。最终lo == hi时，这个值就是第一个可行时间。这个套路能覆盖绝大多数二分答案题，建议直接当作默认写法。
4.2 sqrt 差一点，判题就 WA
浮点是二分题最常见的暗箭。sqrt(1 + 8.0 * totalSeconds / w)算出来可能比真实值小一点，直接long long截断后会造成 1 的偏差。有人会写floor((sqrt(...) - 1) / 2 + 1e-9)，但1e-9这种魔法值在另一组数据上可能加过头，或者仍然不够。
我自己的经验是：完全不依赖精度常数，老老实实加修正循环。先根据浮点结果给一个初始x，然后往上走到不能走为止，再往下退到合法位置。两次 while 最多跑两三轮，在n只有 10^4 的规模下，时间成本可以忽略。正确性是第一位的，省这几行浮点修正的代价可能是几十分钟的 debug 时间。
4.3 中间乘法溢出，long long 也不一定稳
w * (x + 1) * (x + 2) / 2这种写法，在 C++ 里是从左到右计算的。如果w是int，x + 1是long long，第一步会先把w提升成long long，一般没大问题。但如果你图省事把变量都写成int，在极端数据下中间乘积直接溢出成负数，后面所有比较全错。
比赛时我建议所有参与乘法运算的变量都统一用long long，并且在比较前先判断数量级。如果题目数据范围再大一点，比如mountainHeight到 10^6，那w * x * (x + 1)的中间结果可能接近 10^18 的极限，这种时候直接用__int128最安心。性能上不会差太多，但能彻底干掉一类隐蔽的错误。
4.4 check 里对每个工人再二分，容易被卡
一种常见的超时写法是：在 check 函数里对每个工人再二分一次找最大x，也就是外层二分套内层二分，复杂度变成O(n log^2 Ans)。如果n是 10^4，log Ans约 60，二重循环就是 10^4 * 60 * 60 = 3600 万次，很多题目能过，但没必要。
用一元二次方程求出近似解，再修正到整数，每个工人是常数时间，整个 check 是O(n)，总复杂度O(n log Ans)。差距在多次调用 check 后被放大。尤其是周赛题目的测试数据往往比较极限，养成“能用数学就不嵌套二分”的习惯，后面遇到类似题会非常受益。
4.5 别把“完成”理解成“恰好挖完”
有人在 check 里写sum == mountainHeight，这是错的。多挖一点完全没关系，山的高度归零就算完成，系统不会要求工人停下来时一分不差。所以判定条件应该是sum >= mountainHeight。
这类“至少/不超过”的方向问题看起来很基础，但周赛现场仍然有人翻车，因为样例数据可能恰好全部整除，把问题掩盖了，隐藏数据才暴露。写判定条件时，先想清楚题目说的是“至少需要”还是“恰好等于”，这是一个一分钟能规避的坑。
5. 扩展：如果把题目改一改，解法要怎么动
5.1 如果要求每个工人都必须参与
比如题目加一句“每个工人至少降低 1 米”，判定函数就不能只算“最大能挖多少”，还要保证每个人都分到至少 1。最直接的办法是在 check 里先为每个工人预留 1 米，观察总时间是否够最低下限，再用剩余时间算最大产出。每个人干 1 米的最小开销是workerTimes[i]，如果总时间连这个都不够，直接返回 false。
这个变体的难点不是二分，而是 check 里要同时处理“强制性最低工作量”和“剩余可分配工作量”。二分框架完全不变，变的只是细节。遇到这种修改，先写出来，再用几个有代表性的样例验证，你会发现核心思路没有变化。
5.2 如果工时函数改成平方而不是等差
假如工人第k米的成本不是w * k，而是w * k^2，那么总成本公式会变成：
w * x * (x + 1) * (2x + 1) / 6这个函数依然关于x单调递增，所以依然可以二分答案。最大x的求解从一元二次方程变成三次方程，可以继续用浮点近似加修正循环。这个思路对所有“工人的累计产出随工作量单调递增”的问题都通用。
反过来，如果有人把成本改成w * 2^k，虽然同样是单调，但增长速度爆炸。二分依然可用，只是上界要小心，避免二分的搜索区间过大影响性能。遇到这种增长极快的函数，倍增添上界会很有用，因为你不需要手工预估答案上限，直接让程序试探到可行为止。
5.3 如果没有“同时并行”，而是串行作业
串行版本会变成另一个问题：一个工人做完后另一个再开始，求最少总时间。那就不应该对时间二分，因为时间不是并行消耗的；应该考虑动态规划或优先队列调度。并行与串行的区别，决定了搜索对象是“时间”还是“分配策略”。
3296 里明确说了所有工人同时工作，所以时间这个维度天然适合二分。比赛里读题时一定要先确认“并行”这个词，它直接决定算法方向。如果你发现题目没有说并行，默认串行，那反而要警惕是不是应该换一种模型。
结尾
我个人在周赛里第一次写这题时，也在 check 的浮点修正上翻过车：样例过了，一交就 WA，后来发现是sqrt偏差导致某个工人少算了一米。从那以后养成了一个习惯：凡是二分答案题，check 里所有“算最大可行量”的部分，一律先给一个粗略近似，再写两个方向的 while 修正，免疫一切浮点和边界问题。
另一个小技巧是在本地把所有极端样例跑一遍：mountainHeight = 1、workerTimes全为最大值、只有一个工人、所有工人速度都一样。把这几个场景枚举完，比反复盯着评测机的 WA 结果猜原因效率高得多。这道题的模型本身不复杂，但把“近似加校正”和“边界分类验证”这一套习惯固化下来，以后再遇到任何二分答案的新壳子，你都能比对手快半拍。
