Show problems as
Classic problem #2528HardArrayBinary SearchGreedyQueueSliding WindowPrefix Sum

Maximize the Minimum Powered City

Real-world version: Lift the Weakest Relay Stop
Tracked in this browser only
Read Maximize the Minimum Powered City on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A single road has n numbered stops. stations[i] is how many relay masts stand at stop i. A mast standing at stop j puts signal on every stop i with |i - j| <= r, so the signal at stop i is the number of masts standing at stops within r of it, counting every mast at every such stop.

You may erect k further masts. Each one has to stand at one of the n stops, several new masts may share a stop, and they may share a stop with existing masts. You do not have to erect all k.

Return the largest value the weakest stop's signal can be raised to, that is the largest possible value of the smallest signal over all n stops.

Examples

Example 1

Input
stations = [1, 2, 4, 5, 0], r = 1, k = 2
Output
5

The starting signals are 3, 7, 11, 9 and 5. Erecting both new masts at stop 1 gives the stop counts [1, 4, 4, 5, 0] and signals 5, 9, 13, 9 and 5, so the weakest stop reads 5.

Example 2

Input
stations = [0, 0, 0], r = 1, k = 1
Output
1

A single mast at stop 1 reaches stops 0, 1 and 2, so every stop reads 1.

Example 3

Input
stations = [4, 4, 4, 4], r = 0, k = 0
Output
4

With a reach of 0 each stop only sees its own masts, and no new mast may be erected, so the weakest signal stays at 4.

Constraints

  • n == stations.length
  • 1 <= n <= 10^5
  • 0 <= stations[i] <= 10^5
  • 0 <= r <= n - 1
  • 0 <= k <= 10^9
  • The answer never exceeds 1.1 * 10^10.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_power(stations: list[int], r: int, k: int) -> int:
Java
public long maxPower(int[] stations, int r, int k)

More on the same topics