Welcome to Subscribe On Youtube
2528. Maximize the Minimum Powered City
Description
You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the ith city.
Each power station can provide power to every city in a fixed range. In other words, if the range is denoted by r, then a power station at city i can provide power to all cities j such that |i - j| <= r and 0 <= i, j <= n - 1.
- Note that
|x|denotes absolute value. For example,|7 - 5| = 2and|3 - 10| = 7.
The power of a city is the total number of power stations it is being provided power from.
The government has sanctioned building k more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.
Given the two integers r and k, return the maximum possible minimum power of a city, if the additional power stations are built optimally.
Note that you can build the k power stations in multiple cities.
Example 1:
Input: stations = [1,2,4,5,0], r = 1, k = 2 Output: 5 Explanation: One of the optimal ways is to install both the power stations at city 1. So stations will become [1,4,4,5,0]. - City 0 is provided by 1 + 4 = 5 power stations. - City 1 is provided by 1 + 4 + 4 = 9 power stations. - City 2 is provided by 4 + 4 + 5 = 13 power stations. - City 3 is provided by 5 + 4 = 9 power stations. - City 4 is provided by 5 + 0 = 5 power stations. So the minimum power of a city is 5. Since it is not possible to obtain a larger power, we return 5.
Example 2:
Input: stations = [4,4,4,4], r = 0, k = 3 Output: 4 Explanation: It can be proved that we cannot make the minimum power of a city greater than 4.
Constraints:
n == stations.length1 <= n <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109
Solutions
-
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; } }; -
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 -
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) } -
function maxPower(stations: number[], r: number, k: number): number { function check(x: bigint, k: bigint): boolean { d.fill(0n); let t = 0n; for (let i = 0; i < n; ++i) { t += d[i]; const dist = x - (s[i] + t); if (dist > 0) { if (k < dist) { return false; } k -= dist; const j = Math.min(i + r, n - 1); const left = Math.max(0, j - r); const right = Math.min(j + r, n - 1); d[left] += dist; d[right + 1] -= dist; t += dist; } } return true; } const n = stations.length; const d: bigint[] = new Array(n + 1).fill(0n); const s: bigint[] = new Array(n + 1).fill(0n); for (let i = 0; i < n; ++i) { const left = Math.max(0, i - r); const right = Math.min(i + r, n - 1); d[left] += BigInt(stations[i]); d[right + 1] -= BigInt(stations[i]); } s[0] = d[0]; for (let i = 1; i < n + 1; ++i) { s[i] = s[i - 1] + d[i]; } let left = 0n, right = 1n << 40n; while (left < right) { const mid = (left + right + 1n) >> 1n; if (check(mid, BigInt(k))) { left = mid; } else { right = mid - 1n; } } return Number(left); }