3296. 移山所需的最少秒數

思路

題目滿足單調性：要是工人能在時間 $x$ 之內把山移掉，那麼 $\geq{x}$ 的時間也能做到這件事。
所以可以用二分查找去找出最小的時間。

在檢查給定時間內能否將山移掉時，能利用數學找出每個工人各自能移掉多少山。

程式碼

二分查找

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        int n = workerTimes.size();
        long long left = 1, right = 1e16;
        
        auto isOk = [&](long long limit){ // 給定限制時間 limit, 工人們能否把山移掉。
            long long sum = 0;
            for(int i = 0; i < n; i++) {
                // workerTimes[i] * x * (x + 1) / 2 <= limit
                // x * (x + 1) <= 2 * limit / workerTimes[i]
                long long target = 2 * limit / workerTimes[i];
                // x^2 + x - target = 0
                // a = 1, b = 1, c = -target
                // x = -b ± sqrt(b^2 - 4ac) / 2a
                long long x = (sqrt(1 + 4 * target) - 1) / 2;
                sum += x;
                if(sum >= mountainHeight) return true;
            }
            return false;
        };
        while(left <= right) {
            long long mid = left + (right - left) / 2;
            if(isOk(mid)) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{H})$
• 空間複雜度：$O(1)$