Maximize the Minimum Powered City
Problem
Each city i has stations[i] power stations. A station at city i powers every city j with |i − j| ≤ r. A city's power is the total stations covering it. You may build k more stations anywhere (multiple allowed per city). Return the largest possible value of the minimum city power.
stations = [1,2,4,5,0], r = 1, k = 25def maxPower(stations, r, k):
n = len(stations)
power = [0] * n # base power of each city
cur = sum(stations[:min(r + 1, n)]) # window [0, r] for city 0
for i in range(n):
if i > 0:
if i + r < n: cur += stations[i + r] # slide right edge in
if i - r - 1 >= 0: cur -= stations[i - r - 1] # slide left edge out
power[i] = cur
def feasible(target):
extra = [0] * n # difference array of built stations
running = 0 # extra coverage reaching city i
used = 0
for i in range(n):
running += extra[i]
p = power[i] + running
if p < target: # city i is too weak
need = target - p
used += need
if used > k: # ran out of budget
return False
running += need # cover city i now
drop = i + 2 * r + 1 # this batch stops covering here
if drop < n: extra[drop] -= need
return True
lo, hi = min(power), min(power) + k # answer lies in this range
while lo < hi:
mid = (lo + hi + 1) // 2
if feasible(mid): lo = mid # mid works, aim higher
else: hi = mid - 1 # mid fails, aim lower
return lofunction maxPower(stations, r, k) {
const n = stations.length;
const power = new Array(n).fill(0); // base power per city
let cur = 0;
for (let i = 0; i <= Math.min(r, n - 1); i++) cur += stations[i];
for (let i = 0; i < n; i++) {
if (i > 0) {
if (i + r < n) cur += stations[i + r]; // slide right edge in
if (i - r - 1 >= 0) cur -= stations[i - r - 1]; // slide left edge out
}
power[i] = cur;
}
function feasible(target) {
const extra = new Array(n).fill(0); // difference array
let running = 0, used = 0;
for (let i = 0; i < n; i++) {
running += extra[i];
const p = power[i] + running;
if (p < target) { // city i too weak
const need = target - p;
used += need;
if (used > k) return false; // out of budget
running += need; // cover city i now
const drop = i + 2 * r + 1; // batch stops covering here
if (drop < n) extra[drop] -= need;
}
}
return true;
}
let lo = Math.min(...power), hi = lo + k; // search range (BigInt-safe in real use)
while (lo < hi) {
const mid = lo + Math.ceil((hi - lo) / 2);
if (feasible(mid)) lo = mid; // mid works, aim higher
else hi = mid - 1; // mid fails, aim lower
}
return lo;
}long maxPower(int[] stations, int r, int k) {
int n = stations.length;
long[] power = new long[n]; // base power per city
long cur = 0;
for (int i = 0; i <= Math.min(r, n - 1); i++) cur += stations[i];
for (int i = 0; i < n; i++) {
if (i > 0) {
if (i + r < n) cur += stations[i + r]; // slide right in
if (i - r - 1 >= 0) cur -= stations[i - r - 1]; // slide left out
}
power[i] = cur;
}
long lo = Long.MAX_VALUE;
for (long p : power) lo = Math.min(lo, p);
long hi = lo + k; // answer in [lo, hi]
while (lo < lo + (hi - lo + 1) / 2 && lo < hi) {
long mid = lo + (hi - lo + 1) / 2;
if (feasible(power, r, k, mid)) lo = mid; // mid works, aim higher
else hi = mid - 1; // mid fails, aim lower
}
return lo;
}
boolean feasible(long[] power, int r, long k, long target) {
int n = power.length;
long[] extra = new long[n]; // difference array
long running = 0, used = 0;
for (int i = 0; i < n; i++) {
running += extra[i];
long p = power[i] + running;
if (p < target) { // city i too weak
long need = target - p;
used += need;
if (used > k) return false; // out of budget
running += need; // cover city i now
int drop = i + 2 * r + 1; // batch stops here
if (drop < n) extra[drop] -= need;
}
}
return true;
}long long maxPower(vector<int>& stations, int r, int k) {
int n = stations.size();
vector<long long> power(n, 0); // base power per city
long long cur = 0;
for (int i = 0; i <= min(r, n - 1); i++) cur += stations[i];
for (int i = 0; i < n; i++) {
if (i > 0) {
if (i + r < n) cur += stations[i + r]; // slide right in
if (i - r - 1 >= 0) cur -= stations[i - r - 1]; // slide left out
}
power[i] = cur;
}
auto feasible = [&](long long target) -> bool {
vector<long long> extra(n, 0); // difference array
long long running = 0, used = 0;
for (int i = 0; i < n; i++) {
running += extra[i];
long long p = power[i] + running;
if (p < target) { // city i too weak
long long need = target - p;
used += need;
if (used > k) return false; // out of budget
running += need; // cover city i now
int drop = i + 2 * r + 1; // batch stops here
if (drop < n) extra[drop] -= need;
}
}
return true;
};
long long lo = *min_element(power.begin(), power.end());
long long hi = lo + k; // answer in [lo, hi]
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (feasible(mid)) lo = mid; // mid works, aim higher
else hi = mid - 1; // mid fails, aim lower
}
return lo;
}Explanation
The answer is monotone: if we can guarantee every city has power at least t, we can certainly guarantee at least t − 1 (just don't use some stations). That monotonicity is the signal to binary search the answer — the final minimum power itself.
First we compute each city's base power with a sliding window of radius r. City i is covered by stations in [i − r, i + r], so as i advances by one we add the station entering on the right and drop the one leaving on the left. That is an O(n) sweep, no nested loops.
For a candidate minimum target, the feasible(target) check sweeps left to right and is greedy: when city i is still below target, the only stations that can still help it are placed at city i + r (any further right would not reach i). Building them there pushes their coverage as far right as possible, helping the most future cities, so it is always the optimal placement.
We never rebuild the array. A difference array extra plus a running total acts like a queue of active contributions: each batch of need stations added at city i + r covers cities [i, i + 2r], and we schedule a subtraction at i + 2r + 1 so it expires exactly when its window ends. If the cumulative used ever exceeds k, the target is infeasible.
The search range is [min(power), min(power) + k]: even if we dump all k stations onto the single weakest city, its power rises by at most k, so no larger minimum is reachable. We keep the largest target for which feasible returns true.
Example: stations = [1,2,4,5,0], r = 1, k = 2. Base powers are [3,7,11,9,5], minimum 3. Binary searching in [3,5], every candidate up to 5 is feasible (placing both extras at city 1 lifts city 0 and city 4 region appropriately), and 6 is not — so the answer is 5.