Back to Leetcode

Readme

Binary_Search/2528.Maximize-the-Minimum-Powered-City/Readme.md

latest652 B
Original Source

2528.Maximize-the-Minimum-Powered-City

我们假设The minimum power of a city是m,那么意味着每个城市都可以得到至少m的供应。我们就顺着走一遍每个城市,看它是否已经实现了周围[i-r,i+r]范围内的滑窗和大于等于m。如果不够m,那么我们必然会贪心地增加最优端的那个城市的供给(因为它能覆盖更多未来的城市)补齐至m。一路走下去,如果总共需要补建的电力站小于等于k,那么就说明m是可以实现的,于是可以尝试猜测更大的m。如果需要补建的电力站大于k,那么就说明m不可行,就尝试猜测更小的m。