洛谷3378

某一个“天”

我突发奇想用的python列表加bif做的（
结果tle 了，改怎么优化

1. from sys import stdin
   
2. 
   
3. lst=[]
   
4. a=stdin.read()
   
5. n=int(a.split("\n")[0])
   
6. for i in a.split("\n")[1:n+1]:
   
7.     if eval(i[0])==1:
   
8.         lst.append(int(i.split(' ')[1]))
   
9.     elif eval(i[0])==2:
   
10.         print(min(lst))
    
11.     else:
    
12.         lst.remove(min(lst))
    
13.         

复制代码

FishC

鱼油你好！ 你的程序TLE 主要是因为每次查找最小值都调用min(lst)（O(n)），删除最小值时lst.remove(min(lst))也是O(n)扫描两次，整体效率极低。对于洛谷P3378这类需要频繁插入、取最小、删除最小的题目，必须用优先队列（堆）。Python自带heapq模块实现最小堆，插入和删除都是O(log n)，能完美避开TLE。

以下是优化后的代码（使用堆，读取用sys.stdin.buffer.read加快速度）：

1. 
   
2. from sys import stdin
   
3. import heapq
   
4. 
   
5. data = stdin.buffer.read().split()
   
6. n = int(data[0])
   
7. heap = []
   
8. idx = 1  # 当前读取位置
   
9. 
   
10. for _ in range(n):
    
11.     op = int(data[idx]); idx += 1
    
12.     if op == 1:
    
13.         x = int(data[idx]); idx += 1
    
14.         heapq.heappush(heap, x)
    
15.     elif op == 2:
    
16.         print(heap[0])  # 堆顶即最小值
    
17.     else:  # op == 3
    
18.         heapq.heappop(heap)  # 删除最小元素
    

复制代码

几个要点：
- 不要用eval()处理指令，直接按空格分割取数字即可，速度更快。
- heap[0]就是最小值，且heappop直接移除最小元素。
- 输入用stdin.buffer.read()一次性读取全部，然后用.split()切割，避免逐行处理的开销。

这样修改后，单次操作复杂度降低两个数量级，轻松AC。希望能帮到你~

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。