2528. 最大化城市的最小電量

思路

因為一個城市能供電的範圍，以自己為中心，半徑長為r，
所以對於第i座城市來說，能影響到自己的城市範圍在i - r到 i + r之間。
首先要計算出每個城市現有的電量energy[i]是多少，
這可以用前綴和或是滑動窗口做到，將複雜度從 $O(n^2)$ 降低到 $O(n)$。

再來要判斷加入k的發電廠之後，最大化「電力最少的城市」，也就是要盡量讓所有城市中，電量的最小值最大化。
這裡用二分查找去解，假設這個數值叫做low，然後看看有沒有辦法在多加最多k的發電廠的情況下，去滿足條件。

假如現在的城市i需要多兩單位電力去滿足最低要求的low，
需要多擺兩個電塔到自己或是附近（i - r ~ i + r）的城市裡面。

因為遍歷時是從前面往後，表示在i之前的城市電力都已經足夠，
貪心的去想，自然要把這兩個電塔放到i + r這個位置上面(記得不要超範圍)。

加入的電塔會影響到在i ~ i + 2r之間的數字，
會讓這個區間的城市都加上一個固定的數值，用上面的例子就是2，
在區間上增加固定的數值，能用差分數組將這個 $O(n)$ 操作簡化為 $O(1)$ 。

程式碼

前綴和 + 二分查找 + 貪心 + 差分數組

class Solution {
public:
    long long maxPower(vector<int>& stations, int r, int k) {
        int n = stations.size();
        long long mn = LLONG_MAX;
        vector<long long> sum(n + 1);
        for(int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + stations[i];
        }
        vector<long long> energy(n, 0);
        for(int i = 0; i < n; ++i) {
            energy[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)];
            mn = min(mn, energy[i]);
        }
        auto check = [&](long long low) -> bool {
            vector<long long> diff(n + 1);
            long long sum_diff = 0, built = 0;
            for(int i = 0; i < n; ++i) {
                sum_diff += diff[i];
                // 現在有的電塔 = 原本有的電塔 energy[i] + 前面遍歷後，加上的電塔(sum_diff)
                // 需要的電塔 = 目標 - 現在有的電塔
                long long need = low - (energy[i] + sum_diff); 
                if(need <= 0) {
                    continue;
                }
                built += need; // 蓋電塔
                if(built > k) { // 超出限制
                    return false;
                }
                // 蓋的電塔要盡量涵蓋越多範圍越好，但要碰到現在的位置，
                sum_diff += need; // 前面加 (diff[i] += need)
                diff[min(i + r * 2 + 1, n)] -= need; // 後面減, 相當於區域遞增
            }
            return true;
        };
        // 開區間二分
        long long left = mn + k / n, right = mn + k + 1; // left = 平均分, right = 全放到最小
        while(left + 1 < right) {
            long long mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
        // 閉區間二分
        // long long left = mn + k / n - 1, right = mn + k + 1;
        // while(left <= right) {
        //     long long mid = left + (right - left) / 2;
        //     if(check(mid)) { 
        //         left = mid + 1;
        //     }
        //     else { 
        //         right = mid - 1;
        //     }
        // }
        // return right;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{k})$, n是station的長度，二分查找$O(\log{k})$
• 空間複雜度：$O(n)$