#2528
Maximize the Minimum Powered City
expert · 1145 · lc hard +32 · verified · 61.8% accepted · 868 likes · top 62%
Description
Given a 0-indexed array stations where stations[i] is the number of power plants in city i, each plant covers all cities within range r (i.e., |i - j| <= r). The power of a city is the count of plants covering it. You may build k additional plants in any cities (same range r). Return the maximum achievable minimum power across all cities after optimally placing the new plants.
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.
Code
1
2
3