给你一个下标从 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 <= 105
0 <= stations[i] <= 105
0 <= r <= n - 1
0 <= k <= 109
方法一:二分查找 + 差分数组 + 贪心
根据题目描述,最小供电站数目随着
我们先利用差分数组以及前缀和算出初始时每座城市的供电站数目,记录在数组
接下来,我们定义二分查找的左边界为
函数
遍历每座城市,如果当前城市 false
。否则遍历结束后,返回 true
。
时间复杂度
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
def check(x, k):
d = [0] * (n + 1)
t = 0
for i in range(n):
t += d[i]
dist = x - (s[i] + t)
if dist > 0:
if k < dist:
return False
k -= dist
j = min(i + r, n - 1)
left, right = max(0, j - r), min(j + r, n - 1)
d[left] += dist
d[right + 1] -= dist
t += dist
return True
n = len(stations)
d = [0] * (n + 1)
for i, v in enumerate(stations):
left, right = max(0, i - r), min(i + r, n - 1)
d[left] += v
d[right + 1] -= v
s = list(accumulate(d))
left, right = 0, 1 << 40
while left < right:
mid = (left + right + 1) >> 1
if check(mid, k):
left = mid
else:
right = mid - 1
return left
class Solution {
private long[] s;
private long[] d;
private int n;
public long maxPower(int[] stations, int r, int k) {
n = stations.length;
d = new long[n + 1];
s = new long[n + 1];
for (int i = 0; i < n; ++i) {
int left = Math.max(0, i - r), right = Math.min(i + r, n - 1);
d[left] += stations[i];
d[right + 1] -= stations[i];
}
s[0] = d[0];
for (int i = 1; i < n + 1; ++i) {
s[i] = s[i - 1] + d[i];
}
long left = 0, right = 1l << 40;
while (left < right) {
long mid = (left + right + 1) >>> 1;
if (check(mid, r, k)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean check(long x, int r, int k) {
Arrays.fill(d, 0);
long t = 0;
for (int i = 0; i < n; ++i) {
t += d[i];
long dist = x - (s[i] + t);
if (dist > 0) {
if (k < dist) {
return false;
}
k -= dist;
int j = Math.min(i + r, n - 1);
int left = Math.max(0, j - r), right = Math.min(j + r, n - 1);
d[left] += dist;
d[right + 1] -= dist;
t += dist;
}
}
return true;
}
}
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k) {
int n = stations.size();
long d[n + 1];
memset(d, 0, sizeof d);
for (int i = 0; i < n; ++i) {
int left = max(0, i - r), right = min(i + r, n - 1);
d[left] += stations[i];
d[right + 1] -= stations[i];
}
long s[n + 1];
s[0] = d[0];
for (int i = 1; i < n + 1; ++i) {
s[i] = s[i - 1] + d[i];
}
auto check = [&](long x, int k) {
memset(d, 0, sizeof d);
long t = 0;
for (int i = 0; i < n; ++i) {
t += d[i];
long dist = x - (s[i] + t);
if (dist > 0) {
if (k < dist) {
return false;
}
k -= dist;
int j = min(i + r, n - 1);
int left = max(0, j - r), right = min(j + r, n - 1);
d[left] += dist;
d[right + 1] -= dist;
t += dist;
}
}
return true;
};
long left = 0, right = 1e12;
while (left < right) {
long mid = (left + right + 1) >> 1;
if (check(mid, k)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
};
func maxPower(stations []int, r int, k int) int64 {
n := len(stations)
d := make([]int, n+1)
s := make([]int, n+1)
for i, v := range stations {
left, right := max(0, i-r), min(i+r, n-1)
d[left] += v
d[right+1] -= v
}
s[0] = d[0]
for i := 1; i < n+1; i++ {
s[i] = s[i-1] + d[i]
}
check := func(x, k int) bool {
d := make([]int, n+1)
t := 0
for i := range stations {
t += d[i]
dist := x - (s[i] + t)
if dist > 0 {
if k < dist {
return false
}
k -= dist
j := min(i+r, n-1)
left, right := max(0, j-r), min(j+r, n-1)
d[left] += dist
d[right+1] -= dist
t += dist
}
}
return true
}
left, right := 0, 1<<40
for left < right {
mid := (left + right + 1) >> 1
if check(mid, k) {
left = mid
} else {
right = mid - 1
}
}
return int64(left)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}