2141. 同時運行 N 台電腦的最長時間

思路

要找到讓電腦同時運行的最長時間，我們能夠「猜猜看」它能運行多久的時間，
然後驗證這個猜的數字是否合理。

運行的最糟情況就是運行 0 個時間單位，
最好的情況是將「電池電量總和」平分給 n 台電腦所得到的時間單位。
因此猜的範圍是0 ~ (sum / n) + 1。

猜時越長的數字就越不可能，相當於限制越來越多，
假如一個高限制的數字可能滿足，那麼更低限制的時間就不用猜了，肯定都可以。

B：假如高難度關卡你都打的過，那也不用再打低難度關卡去測試了。
A：為了避免各種莫名其妙的追問（比如高難度關卡測試的方面跟低難度不同），假設關卡完全相同，只有數值的提升。

接下來要驗證猜的數字（運行長短）合不合理。 假設我們猜的數字叫做mid，要想讓所有電腦運行這麼長的時間，至少要有n * mid這麼多的電量存在。

對於每個電池，

• 假如電池電量 >= mid，一顆電池就能確保一台電腦在mid時間中不會被關掉。
• 假如電池電量 < mid，需要多個電池，以確保電腦在mid時間終不會被關掉。 所以在判斷時，在電池電量跟mid當中取最小值。

程式碼

二分查找

class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        long long left = 0, right = reduce(batteries.begin(), batteries.end(), 0LL) / n + 1;   
        while(left <= right) {
            long long mid = left + (right - left) / 2;
            long long sum = 0;
            for(long long b: batteries) {
                sum += min(b, mid); //「最低要求」跟「電池電量」當中取最小值
            }
            if(sum >= n * mid) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return right;
    }
};

複雜度分析

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