全面溃败==
第二题就卡了好久 好白痴
最后用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