LeetCode 3296 移山所需最少秒数：二分答案与判定函数详解-北京尧图网络

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 1T 3。公式根为(sqrt(1 24) - 1) / 2 (5 - 1) / 2 2所以x 2校验1 * 2 * 3 / 2 3 3通过。再看w 2T 5根约为(sqrt(1 20) - 1) / 2 ≈ 1.79向下取整是 1校验x 1时2 * 1 * 2 / 2 2 5x 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 longJava 用long。真正危险的是计算w * (x 1) * (x 2) / 2时中间乘积可能较大。题目约束下 long long 基本够用但如果你在写自己的题解库想覆盖更泛化的场景可以在乘法那一步用__int128或者把乘法拆开降低中间值大小。3. 完整代码与实现细节3.1 C17 示例与逐行解释现在把上面思路变成可以直接跑的代码。我会在代码里注释每一步在干什么方便复盘。class Solution { public: long long minimumSeconds(int mountainHeight, vectorint 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 3workerTimes [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 1workerTimes [5]答案显然是 5。代码里ok(0)为 false二分最终会让lo和hi收敛到 5。如果mountainHeight 4workerTimes [1, 1, 1]T 2时每个工人最多降 1 米三人合计 3不够T 3时每个工人最多降 2 米三人合计 6够了。答案是 3不是 4因为三个人都并行工作第 3 秒已经能创造出 6 米的总降低量。4. 踩坑记从 0 到 AC 最常见的五个坑4.1 二分边界写错直接死循环二分答案最常见的错误不是 check 写错而是边界更新写错。有些人把lo初始化为 1hi初始化得很大然后写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是intx 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^4log 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 结果猜原因效率高得多。这道题的模型本身不复杂但把“近似加校正”和“边界分类验证”这一套习惯固化下来以后再遇到任何二分答案的新壳子你都能比对手快半拍。

LeetCode 3296 移山所需最少秒数：二分答案与判定函数详解

相关推荐

水质检测系统源码实战：Java+阿里云数据库构建稳定数据链路

Multisim仿真+AD2实测：用μA741复刻三角波-方波发生器

Java工程师如何开发AI Agent：从概念到工程实践

更多资讯

【题解-洛谷】P1478 陶陶摘苹果（升级版）

Java毕设实战：SpringBoot+Vue小说平台全栈开发指南

Actor模型与Goroutine深度解析：系统编程开源教材Coursebook并发模型完全指南

如何用Orkas驱动Claude Code与Codex：3步把你的编程CLI接入本地智能体团队

SpringBoot+uni-app驾考系统全栈毕设实战指南

动态批处理中的抢占与优先级调度：Chunked Prefill 消除解码长尾延迟

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？