[M二分答案] lc3296. 移山所需的最少秒数(二分答案+周赛416_2+好题)

1. 题目来源

链接：3296. 移山所需的最少秒数

2. 题目解析

同样一道很经典的二分答案问题哈。

思路：

• 二分答案最小时间。计算当前时间下，每个工人能挖掘的最大的高度是多少的总和。
• 如果总和 >= mountainHeight。说明可以挖掘完，r = mid
• 如果总和 < mountainHeight。说明挖掘不完，l = mid + 1

值得注意的是，这里不仅需要二分时间这个答案值，在计算每个工人能挖掘的最大高度的总和时，也是需要通过二分来进行计算的。因为对于限定的 t 时间下，工人最多的挖掘高度无非就是 mountainHeight，工人挖掘速度为 1，那么这里的挖掘高度就等价于工人挖掘的时间。

在 mid 时间下，根据题意的计算方式，工人的耗时为：(1+mid)*mid/2 等差数列求和即可。总消耗时间则为：(1+mid)*mid/2 * x 判断它是否在 t 时间内。超过了说明挖不到 mid 高度，反之则可以挖到 mid 高度。

---

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(1)$

---

代码：

常规写法：

class Solution {
public:long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {typedef long long LL;auto check = [&](LL t) {LL res = 0;for (int x : workerTimes) {LL l = 0, r = mountainHeight;while (l < r) {LL mid = l + r + 1 >> 1;if (1LL * (mid + 1) * mid / 2 * x <= t) l = mid;else r = mid - 1;}res += l;if (res >= mountainHeight) break;}return res;};LL l = 0, r = 1e18;while (l < r) {LL mid = l + r >> 1;if (check(mid) >= mountainHeight) r = mid;else l = mid + 1;}return l;}
};