# 2528. Maximize the Minimum Powered City
###### tags: `Leetcode` `Hard` `Binary Search` `Sliding Window`
Link: https://leetcode.com/problems/maximize-the-minimum-powered-city/description/
## 思路
思路参考[这里](https://leetcode.com/problems/maximize-the-minimum-powered-city/solutions/3014943/python-binary-search-greedy-sliding-window-very-clear-explanation/?orderBy=most_votes)
binary search by value找出当有k个额外的station时 最大的minPowerRequired
那么如何判断一个minPowerRequired是不是possible的呢
答案是用sliding window 当发现在位置i station数目小于minPowerRequired时 我们把额外的station 建在i+r是最optimal的解法
## Code

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        
        def isPossible(minPowerRequired, remainStation):
            windowPower = 0
            for i in range(min(r-1, n-1)+1):
                windowPower += stations[i]
            additions  = [0]*n
            for i in range(n):
                if i+r<n: windowPower+=stations[i+r]+additions[i+r]
                if i-r-1>=0: windowPower-=stations[i-r-1]+additions[i-r-1]
                if windowPower<minPowerRequired:
                    need = minPowerRequired-windowPower
                    if need>remainStation: return False
                    additions[min(n-1, i+r)] += need
                    windowPower += need
                    remainStation -= need
            return True

        left = 0
        right = sum(stations)+k+1
        while left<right:
            mid = left+(right-left)//2
            if isPossible(mid, k):
                left = mid+1
            else: right = mid
        return left-1