# 2528. Maximize the Minimum Powered City        • Time: $O(n(\Sigma |\texttt{stations[i]}| + k))$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public: long long maxPower(vector& stations, int r, int k) { long long left = ranges::min(stations); long long right = accumulate(stations.begin(), stations.end(), 0LL) + k + 1; while (left < right) { const long long mid = (left + right) / 2; if (check(stations, r, k, mid)) left = mid + 1; else right = mid; } return left - 1; } private: // Returns true if each city can have at least minPower. bool check(vector stations, int r, int additionalStations, long long minPower) { const int n = stations.size(); // Initilaize power as 0-th city's power - stations[r]. long long power = accumulate(stations.begin(), stations.begin() + r, 0LL); for (int i = 0; i < n; ++i) { if (i + r < n) power += stations[i + r]; // power = sum(stations[i - r..i + r]). if (power < minPower) { const long long requiredPower = minPower - power; if (requiredPower > additionalStations) // No enough stations to plant. return false; // Greedily plant requiredPower power stations in the farthest place // to cover as many cities as possible. stations[min(n - 1, i + r)] += requiredPower; additionalStations -= requiredPower; power += requiredPower; } if (i - r >= 0) power -= stations[i - r]; } return true; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public long maxPower(int[] stations, int r, int k) { long left = Arrays.stream(stations).min().getAsInt(); long right = Arrays.stream(stations).asLongStream().sum() + k + 1; while (left < right) { final long mid = (left + right) / 2; if (check(stations.clone(), r, k, mid)) left = mid + 1; else right = mid; } return left - 1; } // Returns true if each city can have at least minPower. boolean check(int[] stations, int r, int additionalStations, long minPower) { final int n = stations.length; // Initilaize power as 0-th city's power - stations[r]. long power = 0; for (int i = 0; i < r; ++i) power += stations[i]; for (int i = 0; i < n; ++i) { if (i + r < n) power += stations[i + r]; // power = sum(stations[i - r..i + r]). if (power < minPower) { final long requiredPower = minPower - power; if (requiredPower > additionalStations) // No enough stations to plant. return false; // Greedily plant requiredPower power stations in the farthest place // to cover as many cities as possible. stations[Math.min(n - 1, i + r)] += requiredPower; additionalStations -= requiredPower; power += requiredPower; } if (i - r >= 0) power -= stations[i - r]; } return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution: def maxPower(self, stations: List[int], r: int, k: int) -> int: n = len(stations) left = min(stations) right = sum(stations) + k + 1 # Returns true if each city can have at least minPower. def check(stations: List[int], additionalStations: int, minPower: int) -> bool: # Initilaize power as 0-th city's power - stations[r]. power = sum(stations[:r]) for i in range(n): if i + r < n: power += stations[i + r] # power = sum(stations[i - r..i + r]). if power < minPower: requiredPower = minPower - power if requiredPower > additionalStations: # No enough stations to plant. return False # Greedily plant requiredPower power stations in the farthest place # to cover as many cities as possible. stations[min(n - 1, i + r)] += requiredPower additionalStations -= requiredPower power += requiredPower if i - r >= 0: power -= stations[i - r] return True while left < right: mid = (left + right) // 2 if check(stations.copy(), k, mid): left = mid + 1 else: right = mid return left - 1