Re: [閒聊] Weekly Contest 409

[DJYOMIYAHINA (通通打死)]

全面潰敗==

第二題就卡了好久 好白癡
最後用dijkstra過了

第三題就 始終TLE
一生就這樣了
就大概知道要maintain目前shortest path
但沒有找到很好的pop方法

def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) ->
List[int]:
    shortest_path = set()
    for i in range(n):
        shortest_path.add(i)

    ans = []
    dis = n-1
    for start,end in queries:
        # print(shortest_path)
        if start in shortest_path and end in shortest_path:
            remove_cnt = 0
            for i in range(start+1, end):
                if i in shortest_path:
                    shortest_path.remove(i)
                    remove_cnt += 1
            dis -= remove_cnt
        ans.append(dis)

    return ans


就有想過如果有個有序的container 可以讓我logN內查到要remove的start跟end就可以了
但我不知道哪來那個東西

結果看答案才知道有SortedList這種東西
什麼鬼

def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) ->
List[int]:
    shortest_path = SortedList([i for i in range(n)])

    ans = []
    for start,end in queries:
        start_idx = shortest_path.bisect_right(start)
        end_idx = shortest_path.bisect_left(end)

        for i in reversed(range(start_idx, end_idx)):
            shortest_path.pop(i)

        ans.append(len(shortest_path)-1)

    return ans

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 37.19.205.170 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722744534.A.C45.html
→ Apache: 別卷了
推 dont: 第三題用sortedList pop
→ sixB: 我沒了 我是垃圾
→ sustainer123: 大師
推 nozomizo: 巨佬
 你們都是大師==
※ 編輯: DJYOMIYAHINA (37.19.205.170 日本), 08/04/2024 12:25:13
→ digua: 大師
推 oin1104: 大師 我第三題 寫到吐 我快哭了