我正在解決 CSES、Traffic Lights上的這個問題 ：
有一條長度為 ?? 的街道，其位置編號為 0,1,...,??。最初沒有紅綠燈，但?? 一組紅綠燈接連添加到街道上。
你的任務是計算每次添加后沒有紅綠燈的最長通道的長度。
輸入
第一行包含兩個整數 ?? 和 ??：街道的長度和交通燈組的數量。
然后，下一行包含 n 個整數?? 1 ,?? 2 ,...,?? ??：每組紅綠燈的位置。每個位置都是不同的。
輸出
每次添加后列印沒有交通燈的最長通道的長度。
約束
- 1 ≤ ?? ≤ 10 9
- 1 ≤ ?? ≤ 2?10 5
- 0 < ?? ?? < ??
例子
輸入：
8 3 3 6 2輸出：
5 3 3
所以為了有效解決這樣的問題，我需要一個類似于串列的 Python 資料結構，但元素的搜索和洗掉需要 O(1) 或更類似于集合的資料結構，但我需要能夠插入多個相同的元素并保持順序。我的問題代碼是：
from collections import defaultdict
from bisect import bisect_right , insort
x , n = list(map(int , input().split()))
arr = list(map(int , input().split()))
lens = defaultdict(int)
lens[x] = 1
lights = [0,x]
for ele in arr:
idx = bisect_right(lights , ele)
to_be_removed = lights[idx] - lights[idx-1]
lens[to_be_removed] -= 1
lens[lights[idx]-ele] = 1
lens[ele-lights[idx-1]] = 1
insort(lights , ele)
print(max([x for x in lens.keys() if lens[x]]) , end =" ")
但是這段代碼很慢。在 C 中有一種稱為多集的資料結構。但是在 python 中找不到類似的資料結構。任何幫助表示贊賞。
uj5u.com熱心網友回復：
您擁有的資料結構lens就像一個多重集，也可以作為Counter. 就時間復雜度而言，演算法的瓶頸部分是：
max([x for x in lens.keys() if lens[x]])
這是一個具有線性時間復雜度的操作，因此它使演算法成為二次的。
為了改進演算法的這一部分，我建議使用堆。有heapq它提供了一個最小堆實作。由于您實際上需要一個最大堆，因此您只需使用負長度即可。
其次，insort還具有線性時間復雜度（盡管使用的時間比max()上面的運算式少）。您可以通過使用自平衡搜索樹實作來改進這一點，它沒有標準庫，但有一些庫提供排序串列，例如sortedcontainers.
以下是如何調整代碼以實作這兩個想法：
from collections import defaultdict
from heapq import heappush, heappop
from sortedcontainers import SortedList
x , n = list(map(int , input().split()))
arr = list(map(int , input().split()))
lens = defaultdict(int)
lens[x] = 1
lights = SortedList([0, x]) # For faster insertion
heap = [-x] # Put total width also in a heap
for ele in arr:
idx = lights.bisect_right(ele)
to_be_removed = lights[idx] - lights[idx-1]
lens[to_be_removed] -= 1
# Add widths to the heap when they are the only occurrences
right = lights[idx]-ele
if lens[right] == 0:
heappush(heap, -right)
lens[right] = 1
left = ele-lights[idx-1]
if lens[left] == 0:
heappush(heap, -left)
lens[left] = 1
# Remove the largest width as long as it no longer represents a segment
while lens[-heap[0]] == 0:
heappop(heap)
# The add method is O(logn)
lights.add(ele)
# Just output the largest width in the heap
print(-heap[0], end = " ")
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409383.html
標籤：
上一篇：選擇N個專案，使其屬性平衡
下一篇：generateKeycpp函式