最大化城市的最小供电站数目

题目

2528. 最大化城市的最小供电站数目

---

给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

• |x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小供电站数目的最大值是多少。

这 k 座供电站可以建在多个城市。

示例 1：

输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。

示例 2：

输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。

提示：

• n == stations.length
• 1 <= n <= 10^5
• 0 <= stations[i] <= 10^5
• 0 <= r <= n - 1
• 0 <= k <= 10^9

题解

方法一：

思路

以后遇到 最大化最小值 或 最小化最大值，优先考虑二分。

在第$i$座城市处的发电站可以作用的城市区间为[i-r, i+r]。因此我们先预处理出代表每个城市的电量的数组$t$。

城市$i$的电量是$\sum \limits_{j = max(0,i-r)}^{min(n-1,i+r)}stations[j]$。
我们可以通过求$stations$的前缀数组，在$O(n)$的时间复杂度内求出t数组：令$p[i]$是前i作城市的电量总和，即$p[i] = \sum \limits_{j=0}^{i-1}stations[j]$。这样$t[i] = p[min(n,i+r+1)]-p[max(0, i-r)]$，可以通过一遍遍历求出t数组。

接下来考虑二分答案。

假设通过建造额外的供电站使得所有城市中电力最小值为$x$，设额外的供电站的数量为$f(x)$，$f(x)$是会随着$x$的增大而增大。能够建造的供电站的个数是$k$，显然可以二分法找到最后一个满足的$f(x)<k$的$x$。
如果电力最小值为$x$，我们需要尝试构造使得每座城市的电力都至少为x。这个可以用贪心法来构造：如果构造到第$i$座城市的电力小于$x$，即$t[i]<x$。由于构造后保证了前$i-1$座城市的电力都大于等于$x$，那么我们要贪心地让未构造的城市得到更多的电力，因此在第i+r座城市建立$x-t[i]$座城市可以为区间为[i, i+2*r]的城市都增长$x-t[i]$。累加所建电站数量到$f(x)$。

最后如果$f(x)>k$，说明是不满足，缩小二分区间为左半区间。
否则如果$f(x)\le k$，说明是满足的，缩小二分区间为右半区间。
最后锁定到最后一个满足$f(x)\le k$的x作为答案。

代码

class Solution {
public:
    #define ll long long
    long long maxPower(vector<int>& s, int r, int k) {
        int n = s.size();
        vector<ll> p(n+1);
        for (int i=1; i<=n; i++) {
            p[i] = p[i-1]+s[i-1];
        }
        vector<ll> t;
        for (int i=1; i<=n; i++) {
            t.push_back(p[min(n, i+r)] - p[max(0,i-r-1)]);
            // cout << t.back() << " ";
        }
        int sz = t.size();
        ll L = 0, R = 1e15;
        while (L<R) {
            ll m = L+R>>1;
            vector<int> d(sz);
            ll cnt = 0, pre = 0;
            for (int i=0; i<sz; i++) {
                pre += d[i];
                if (pre+t[i]<m) {
                    cnt += m-pre-t[i];
                    if(i+2*r+1<sz) d[i+2*r+1] -= m-pre-t[i];
                    pre += m-pre-t[i];
                }
            }
            if (cnt > k) {
                R = m;
            } else {
                L = m+1;
            }
        }
        return R-1;
    }
};