Leetcode 2528. Maximize the Minimum Powered City

[Woodyiiiiiii]

这道题是双周赛No.95的第四题。

我的做法是先处理完未加入k个stations前的每个City的power，然后再进一步分配k个stations使得minimum最大。

卡在第二步了。

其实，做法是，观察k值，范围是10^9，又是最大值最小值，所以可见可以通过二分法来求最终结果。

对k二分后，问题变成了如何分配小于k的stations数目使得minimum大于等于mid。

看了解析后，我发现思路是尽可能在从左到右的遍历中把station放到窗口[i-r,i+r]的最右边，因为是从左到右遍历的，能保证左边加油站足够，所以要尽可能地要保证右边的加油站足够，把加油站放尽可能右边(属于辐射题型)。用一个数组add存取提前透支的节点，如此一来便得到递进公式add[i+2*r+1] -= need，用一个变量sum表示前缀和，与add交互。最终看used变量是否超过k。

class Solution {
    public long maxPower(int[] stations, int r, int k) {
        int n = stations.length;
        long[] preSum = new long[n];
        long[] suffixSum = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += stations[i];
            preSum[i] = sum;
        }
        sum = 0;
        for (int i = n - 1; i > 0; i--) {
            sum += stations[i];
            suffixSum[i] = sum;
        }

        long[] stationsPlus = new long[n];
        for (int i = 0; i < n; ++i) {
            stationsPlus[i] = stations[i];
            int left = i - r - 1;
            int right = i + r + 1;
            if (i > 0) {
                stationsPlus[i] += left >= 0 ? preSum[i - 1] - preSum[left] : preSum[i - 1];
            }
            if (i < n - 1) {
                stationsPlus[i] += right < n ? suffixSum[i + 1] - suffixSum[right] : suffixSum[i + 1];
            }
        }

        long lo = 0, high = (long) (1e10 + 1e9 + 1);
        while (lo < high) {
            long mid = (lo + high) / 2;
            if (check(stationsPlus, mid, k, r)) {
                lo = mid + 1;
            } else {
                high = mid;
            }
        }
        return lo - 1;
    }

    private boolean check(long[] stationsPlus, long mid, int k, int r) {
        long used = 0;
        long[] subtract = new long[stationsPlus.length];
        long sum = 0;
        for (int i = 0; i < stationsPlus.length; i++) {
            sum += subtract[i];
            long v = stationsPlus[i] + sum;
            if (v < mid) {
                long need = mid - v;
                used += need;
                sum += need;
                if (i + 2 * r + 1 < stationsPlus.length) {
                    subtract[i + 2 * r + 1] -= need;
                }
            }
        }
        return used <= k;
    }
}

其他辐射类型题目:

• 2086. Minimum Number of Food Buckets to Feed the Hamsters
• 2772. Apply Operations to Make All Array Elements Equal to Zero

tips：
二分左区间值inclusive，右区间exclusive，中间值(lo+high) >> 1，最后返回lo-1

---

• https://leetcode.com/problems/maximize-the-minimum-powered-city/description/