leetcode：1488. 避免洪水泛滥【二分 + 贪心】

分析

先把可以抽干的位置记录下来，用sortedlist的q，方便删除
然后用dict记录某个湖之前是否出现过
如果出现过肯定有pre和now的位置
然后根据pre和now找到q中对应的idx，直接改变这个idx对应的湖即可
模拟贪心二分吧

ac code

from sortedcontainers import SortedList

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        get_drys = SortedList()
        n = len(rains)
        ans = [-1] * n
        for i in range(n):
            if rains[i] == 0:
                get_drys.add(i)
            
        d = defaultdict(int)
        for i in range(1, n + 1):
            if rains[i - 1] > 0:
                if d[rains[i - 1]] == 0:
                    d[rains[i - 1]] = i
                else:
                    pre, now = d[rains[i - 1]] - 1, i - 1
                    idx1 = bisect_left(get_drys, pre)
                    idx2 = bisect_left(get_drys, now)
                    if idx1 == idx2: # no dry option
                        return []
                    else:
                        # pick the first one
                        idx3 = get_drys[idx1]
                        ans[idx3] = rains[i - 1]
                        get_drys.discard(idx3)
                    d[rains[i - 1]] = i
        
        for i in range(n):
            if rains[i] == 0 and ans[i] == -1:
                ans[i] = 1
        
        return ans

总结

二分和贪心