目标
给你一个下标从 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
思路
有 n 个城市，stations[i] 表示第 i 个城市的供电站数目，供电站可以为 r 范围内的城市供电，城市的电量定义为能够为它供电的电站数量。现在计划在这 n 个城市中额外建立 k 座供电站，求所有城市中最小电量的最大值是多少。
最大化最小值考虑枚举答案。贪心策略，如果当前城市供电量小于下限，则需要在 i + r 处建厂，因为前面的都已经满足了，在这里建厂可以更多地提高后面的下限。
代码
/**
* @date 2025-11-07 10:57
*/
public class MaxPower2528 {
public long maxPower(int[] stations, int r, int k) {
int n = stations.length;
long[] diff = new long[n + 1];
long max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, stations[i]);
int left = Math.max(0, i - r);
int right = Math.min(n, i + r + 1);
diff[left] += stations[i];
diff[right] -= stations[i];
}
long left = 0, right = (max + k) * (r + 1);
long m = left + (right - left) / 2;
while (left <= right) {
if (check(diff, m, k, r)) {
left = m + 1;
} else {
right = m - 1;
}
m = left + (right - left) / 2;
}
return right;
}
public boolean check(long[] diff, long target, int k, int r) {
long sum = 0;
int n = diff.length;
long[] tmp = new long[n];
System.arraycopy(diff, 0, tmp, 0, n);
for (int i = 0; i < n - 1; i++) {
sum += tmp[i];
if (sum >= target) {
continue;
}
long c = target - sum;
if (k >= c ) {
tmp[Math.min(n - 1, i + r + r + 1)] -= c;
sum = target;
k -= c;
} else {
return false;
}
}
return true;
}
}
性能
