2528. Maximize the Minimum Powered City Hard

1/**
2 * [2528] Maximize the Minimum Powered City
3 *
4 * 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.
5 * Each power station can provide power to every city in a fixed range. 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.
6 * 
7 * 	Note that |x| denotes absolute value. For example, |7 - 5| = 2 and |3 - 10| = 7.
8 * 
9 * The power of a city is the total number of power stations it is being provided power from.
10 * The government has sanctioned building k more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.
11 * Given the two integers r and k, return the maximum possible minimum power of a city, if the additional power stations are built optimally.
12 * Note that you can build the k power stations in multiple cities.
13 *  
14 * <strong class="example">Example 1:
15 * 
16 * Input: stations = [1,2,4,5,0], r = 1, k = 2
17 * Output: 5
18 * Explanation: 
19 * One of the optimal ways is to install both the power stations at city 1. 
20 * So stations will become [1,4,4,5,0].
21 * - City 0 is provided by 1 + 4 = 5 power stations.
22 * - City 1 is provided by 1 + 4 + 4 = 9 power stations.
23 * - City 2 is provided by 4 + 4 + 5 = 13 power stations.
24 * - City 3 is provided by 5 + 4 = 9 power stations.
25 * - City 4 is provided by 5 + 0 = 5 power stations.
26 * So the minimum power of a city is 5.
27 * Since it is not possible to obtain a larger power, we return 5.
28 * 
29 * <strong class="example">Example 2:
30 * 
31 * Input: stations = [4,4,4,4], r = 0, k = 3
32 * Output: 4
33 * Explanation: 
34 * It can be proved that we cannot make the minimum power of a city greater than 4.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	n == stations.length
40 * 	1 <= n <= 10^5
41 * 	0 <= stations[i] <= 10^5
42 * 	0 <= r <= n - 1
43 * 	0 <= k <= 10^9
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/maximize-the-minimum-powered-city/
49// discuss: https://leetcode.com/problems/maximize-the-minimum-powered-city/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn max_power(stations: Vec<i32>, r: i32, k: i32) -> i64 {
55        
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2528() {
67    }
68}
69