commit 169da2018133b28e107c19278021dcc449362487
parent 6728b04ba3c11d4af85d03bc242a3e4451cd4bab
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 6 Nov 2025 20:57:19 -0700
2528. maximise the minimum powered city
Diffstat:
2 files changed, 126 insertions(+), 0 deletions(-)
diff --git a/max_min_powered_city.c b/max_min_powered_city.c
@@ -0,0 +1,68 @@
+// 2528. Maximize the Minimum Powered City
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'stations' of length 'n' where
+ * 'stations[i]' represents the number of power stations in the i'th city. each
+ * power station can provide every city in a fixed rang.e 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'. the
+ * power of a city is the total number of actions being provided power from. the
+ * government has sanctioned building 'k' more power stations, each of which can
+ * be built in any cit, and have the same range as the pre-existing one. given
+ * the two integers 'r' and 'k', return the maximum possible minimum power of a
+ * city, if the additional power stations are build optimally.
+ */
+
+static bool possible(long long x, int *stations, long long *power, int n, int r,
+ long long k) {
+ long long *diff = (long long *)calloc(n + 1, sizeof(long long)), added = 0;
+ for (int i = 0; i < n; i++) {
+ added += diff[i];
+ long long curr = power[i] + added;
+ if (curr < x) {
+ long long need = x - curr;
+ if (need > k) {
+ free(diff);
+ return false;
+ }
+ k -= need;
+ added += need;
+ int end = i + 2 * r + 1;
+ if (end < n)
+ diff[end] -= need;
+ }
+ }
+ free(diff);
+ return true;
+}
+
+long long maxPower(int *stations, int stationsSize, int r, int k) {
+ long long *prefix = (long long *)calloc(stationsSize + 1, sizeof(long long));
+ long long *power = (long long *)malloc(stationsSize * sizeof(long long));
+ for (int i = 0; i < stationsSize; i++)
+ prefix[i + 1] = prefix[i] + stations[i];
+ for (int i = 0; i < stationsSize; i++) {
+ int left = (i - r < 0) ? 0 : i - r;
+ int right = (i + r >= stationsSize) ? stationsSize - 1 : i + r;
+ power[i] = prefix[right + 1] - prefix[left];
+ }
+ long long low = 0, high = prefix[stationsSize] + k, ans = 0;
+ while (low <= high) {
+ long long mid = low + (high - low) / 2;
+ if (possible(mid, stations, power, stationsSize, r, k)) {
+ ans = mid;
+ low = mid + 1;
+ } else
+ high = mid - 1;
+ }
+ free(prefix);
+ free(power);
+ return ans;
+}
+
+int main() {
+ int s1[] = {1, 2, 4, 5, 0}, s2[] = {4, 4, 4, 4};
+ printf("%lld\n", maxPower(s1, ARRAY_SIZE(s1), 1, 2)); // expect: 5
+ printf("%lld\n", maxPower(s2, ARRAY_SIZE(s2), 0, 3)); // expect: 4
+}
diff --git a/max_min_powered_city.py b/max_min_powered_city.py
@@ -0,0 +1,58 @@
+# 2528. Maximize the Minimum Powered City
+from itertools import accumulate
+
+"""
+you are given a 0-indexed integer array 'stations' of length 'n' where
+'stations[i]' represents the number of power stations in the i'th city. each
+power station can provide every city in a fixed rang.e 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'. the
+power of a city is the total number of actions being provided power from. the
+government has sanctioned building 'k' more power stations, each of which can
+be built in any cit, and have the same range as the pre-existing one. given
+the two integers 'r' and 'k', return the maximum possible minimum power of a
+city, if the additional power stations are build optimally.
+"""
+
+
+class Solution(object):
+ def maxPower(self, stations, r, k):
+ """
+ :type stations: List[int]
+ :type r: int
+ :type k: int
+ :rtype: int
+ """
+ n = len(stations)
+ diff = [0] * (n + 5)
+ for i, j in enumerate(stations):
+ diff[max(0, i - r)] += j
+ diff[min(n - 1, i + r)] -= 1
+ low, high = min(accumulate(diff[:n])), 2 * 10**10
+
+ def possible(mid):
+ df = diff[:]
+ curr, cnt = 0, 0
+ for i in range(n):
+ curr += df[i]
+ if curr < mid:
+ cnt += mid - curr
+ df[min(n - 1, i + 2 * r) + 1] -= mid - curr
+ curr = mid
+ if cnt > k:
+ return False
+ return True
+
+ while low < high:
+ mid = low + high + 1 >> 1
+ if possible(mid):
+ low = mid
+ else:
+ high = mid - 1
+ return low
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxPower(stations=[1, 2, 4, 5, 0], r=1, k=2))
+ print(obj.maxPower(stations=[4, 4, 4, 4], r=0, k=3))
