[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;
    }
};