我正在解决CSES上的这个问题, 交通信号灯:
There is a street of length whose positions are numbered 0,1,…,. Initially there are no traffic lights, but sets of traffic lights are added to the street one after another.
Your task is to calculate the length of the longest passage without traffic lights after each addition.
Input
The first input line contains two integers and : the length of the street and the number of sets of traffic lights.
Then, the next line contains n integers 1,2,…,: the position of each set of traffic lights. Each position is distinct.
Output
Print the length of the longest passage without traffic lights after each addition.
Constraints
- 1 ≤ ≤ 109
- 1 ≤ ≤ 2⋅105
- 0 < <
Example
Input:
8 3 3 6 2
Output:
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++中有一种称为multi-sets的数据结构,但是在Python中找不到类似的数据结构。欢迎任何帮助。
collections.Counter
。 - hilberts_drinking_probleminsort(lights, ele)
是一个O(n)
操作。列表中的max
也是 O(n) 操作。因此,总体复杂度仍然为O(n^2)
。您可以通过维护先前的最大值并基于新部分将插入到哪里来更新最大值部分。您需要搜索和插入都是log(n)
- 因此,您需要 BST/AVL/RB 树来优化,以使整体复杂度为Onlog(n)
,您可以使用 https://pypi.python.org/pypi/bintrees/ - Jay