作者 DJYOMIYAHINA (通通打死)標題 Re: [閒聊] Weekly Contest 409時間 Sun Aug 4 12:08:52 2024
全面潰敗==
第二題就卡了好久 好白癡
最後用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 (日本)
※ 作者: DJYOMIYAHINA 2024-08-04 12:08:52
※ 文章代碼(AID): #1chlxMn5 (Marginalman)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722744534.A.C45.html
推 dont: 第三題用sortedList pop2F 08/04 12:13
→ sixB: 我沒了 我是垃圾3F 08/04 12:13
你們都是大師==
※ 編輯: DJYOMIYAHINA (37.19.205.170 日本), 08/04/2024 12:25:13
→ digua: 大師6F 08/04 12:26
推 oin1104: 大師 我第三題 寫到吐 我快哭了7F 08/04 12:28
--