Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 3296. Minimum Number of Seconds to Make Mountain Height Zero

---

參考資訊：
https://algo.monster/liteproblems/3296

題目：


方法：

Step 1. workerTime * (1 + 2 + 3 + ... + n) = workerTime * n * (n + 1) / 2
Step 2. workerTime * n * (n + 1) / 2 <= timeLimit
Step 3. n^2 + n - 2 * timeLimit / workerTime <= 0
Step 4. n = (-1 + sqrt(1 + 8 * timeLimit / workerTime)) / 2

解答：

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        long l = 0;
        long r = LONG_MAX;

        auto complete = [&](long t) -> bool {
            long v = 0;

            for (auto& w : workerTimes) {
                v += static_cast<long>(sqrt(t * 2.0 / w + 0.25) - 0.5);
            }

            return v >= mountainHeight;
        };

        long ret = 0;
        while (l <= r) {
            long m = l + ((r - l) / 2);

            if (complete(m)) {
                ret = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        return ret;
    }
};