洛谷3378
我突发奇想用的python列表加bif做的（结果tle 了，改怎么优化
from sys import stdin
lst=[]
a=stdin.read()
n=int(a.split("\n"))
for i in a.split("\n"):
if eval(i)==1:
lst.append(int(i.split(' ')))
elif eval(i)==2:
print(min(lst))
else:
lst.remove(min(lst))
鱼油你好！ 你的程序TLE 主要是因为每次查找最小值都调用min(lst)（O(n)），删除最小值时lst.remove(min(lst))也是O(n)扫描两次，整体效率极低。对于洛谷P3378这类需要频繁插入、取最小、删除最小的题目，必须用优先队列（堆）。Python自带heapq模块实现最小堆，插入和删除都是O(log n)，能完美避开TLE。
以下是优化后的代码（使用堆，读取用sys.stdin.buffer.read加快速度）：
from sys import stdin
import heapq
data = stdin.buffer.read().split()
n = int(data)
heap = []
idx = 1# 当前读取位置
for _ in range(n):
op = int(data); idx += 1
if op == 1:
x = int(data); idx += 1
heapq.heappush(heap, x)
elif op == 2:
print(heap)# 堆顶即最小值
else:# op == 3
heapq.heappop(heap)# 删除最小元素
几个要点：
- 不要用eval()处理指令，直接按空格分割取数字即可，速度更快。
- heap就是最小值，且heappop直接移除最小元素。
- 输入用stdin.buffer.read()一次性读取全部，然后用.split()切割，避免逐行处理的开销。
这样修改后，单次操作复杂度降低两个数量级，轻松AC。希望能帮到你~
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]