大家对愚公移山想必都不陌生，今天带来一道移山所需的最少秒数。

阅读完题目，大家想必对题目都有了最基本的概念，那么如何移山，首先想到的便是去模拟这个过程，用回溯的思想，从每个工人的工作时间为0开始，逐渐增加，直至达到所需高度，再去比较哪个时间最短。给出代码如下：

class Solution {
public:
    void sm(long long& Min, int mountainHeight, vector<int>& workerTimes,
            vector<int>& p) {
        int n = 0, t = workerTimes.size();
        for (auto& pn : p) {
            n += pn;
        }
        if (n > mountainHeight) {
            return;
        } else if (n == mountainHeight) {
            long long sum = 0;
            for (int i = 0; i < t; ++i) {
                if (sum < workerTimes[i] * p[i] * (p[i] + 1) / 2) {
                    sum = workerTimes[i] * p[i] * (p[i] + 1) / 2;
                }
            }
            if (Min > sum) {
                Min = sum;
            }
        }
        for (auto& pn : p) {
            pn++;
            sm(Min, mountainHeight, workerTimes, p);
            pn--;
        }
    }

    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        int n = workerTimes.size();
        vector<int> p(n);
        long long Min = LLONG_MAX;
        sm(Min, mountainHeight, workerTimes, p);
        return Min;
    }
};

就是从0开始不断递归，因为工人是并行工作，所以选择工作时间最长的那个，再在都是完成任务的方案中选择时间最少的，看起来很美好，样例也都通过了，但是在测试后，还是超时了，那么这个方法就不行。那么除了这个思路，还可以运用最小堆，先给出代码，方便理解：

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        priority_queue<tuple<long long, long long, int>, vector<tuple<long long, long long, int>>, greater<>> pq;
        for (int t : workerTimes) {
            pq.emplace(t, t, t);
        }

        long long ans = 0;
        while (mountainHeight--) {
            // 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
            auto [total, cur, base] = pq.top(); pq.pop();
            ans = total; // 最后一个出堆的 total 即为答案
            pq.emplace(total + cur + base, cur + base, base);
        }
        return ans;
    }
};

首先来介绍一下，priority_queue既是优先数列，也是最大堆，在compare的那一部分用greater<>便可以转化为最小堆，vector部分为用来存储最小堆的容器，tuple是元组，此处存储三个树为三元组。通过构建一个最小堆，我们便能保证最小堆存储的就是最小的时间。我们构建的最小堆，前三位分别存储的是，该工人总的工作时间，当前高度的工作时间，基础的工作时间。在给最小堆基础赋值的时候，因为工人一开始工作，这三个时间是一样的，所以直接遍历workerTimes赋值。

建立好最小堆后就可以开始遍历了，因为最小堆顶部放的就是当前的最小元素，所以pop后就把最小元素移出堆了。我们每次降低山的高度，为了保证时间更少，我们需要选择当前累计时间更少的工人时间来增加。我们假设工人A时间T1，工人B时间T2，T1<T2，如果A增加，最后输出时间，max(T1 + C1, T2)，如果B增加，最后输出时间，max(T1, T2 + C2)，而T= base×k(k+1)/2，C= base×k，当T1<T2时，C1<C2,所以T1+C1<T2+C2，因为T2<T2 + C2，所以肯定是选择累计时间更少的工人时间增加，最终累计时间更小。

那么理清了这个，一直减小高度就行了，最后输出的元素就是工人中累计时间最多的，也就是答案，而它也是各种方案中最小的，不理解可以再看看第一种方法。

那么除了这个还有没有其他的方法，在第一种方法可以看到求累计时间使用了sum = workerTimes[i] * p[i] * (p[i] + 1) / 2;来求。既然累计时间可以这样求出来，那么我们假设累计时间，不就可以求出工人所能达到的高度。因为工人是并行进行的，那么花费同样的时间，求出他们所能达到的高度，再加起来，假如能大于等于山的高度，那么这个时间就是最小时间。代码如下：

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        long long left = 1;
        long long right = 1e18;  // 足够大的上界
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            
            if (canFinish(mid, mountainHeight, workerTimes)) {
                right = mid;  // 时间足够，尝试更小的
            } else {
                left = mid + 1;  // 时间不够，需要更大的
            }
        }
        
        return left;
    }
    
private:
    bool canFinish(long long time, int mountainHeight, vector<int>& workerTimes) {
        long long totalHeight = 0;
        
        // 遍历每个工人，使用他们各自的时间
        for (int wt : workerTimes) {
            // 每个工人用自己的wt计算最大层数
            long long h = (sqrt(1 + 8.0 * time / wt) - 1) / 2;
            totalHeight += h;
            
            if (totalHeight >= mountainHeight) {
                return true;
            }
        }
        
        return totalHeight >= mountainHeight;
    }
};

我们观察数据：

1 <= mountainHeight <= 105

1 <= workerTimes.length <= 104

1 <= workerTimes[i] <= 106

假设只有一个工人，那么累计时间大约为$T = workerTimes[i] * H * (H+1) / 2 = 10^5 * 10^5 * (10^5+1) / 2 ≈ 10^5 * 10^5 * 10^5 / 2 = 10^15 / 2 = 5 * 10^14$

取1e18基本可以保证，另外LLONG_MAX = 9.22×10^18 ≈ 9.22e18，也不会超出long long范围。

那么就采用二分法来遍历，累计时间，然后再用每个工人的工作时间算出每个工人能达到的层数，再加起来比较，最终如果足够求尝试更小，不够尝试更大，最终就能达到答案。

这道题虽然有三个解法，但是他们是环环相扣的，建议都仔细阅读，充分掌握。