题解 | 小红闯关

在通过某关卡后获得的道具可通过后续的任意关卡，本题想到可采用从后往前遍历的思想，使用大顶堆保存由后往前的关卡通关时长。若通过该关卡后可获得道具，则跳过当前大顶堆中保存的最大时长的关卡。

import heapq                            #引入小顶堆库（python中只有小顶堆，存入元素的负数即可得到大顶堆）
n,k=map(int,input().split())
a=list(map(int,input().split()))
total_time=sum(a)                       #sum(a)获得列表a中所有元素的总和
saved_time=0
pq=[]
heapq.heapify(pq)                       #heapq.heapify(pq)将pq由列表初始化为小顶堆
for i in range(n-1,k-2,-1):
    if (i+1)%k==0 and pq:
        saved_time+=(-heapq.heappop(pq))
    heapq.heappush(pq,-a[i])            #注意加负号，转化为大顶堆
print(total_time-saved_time)