BISHI49　小红闯关¶

中等通过率 21.47%python3样例通过牛客 AC贪心堆

一句话

每通过 k 关得一个跳关道具，用道具跳过的关不花时间。

解题思路¶

这题考什么¶

先把「什么时候能跳」写成约束。跳关也算「通过一关」，所以走到第 i 关之前，已经通过了 i-1 关，手上累计获得 floor((i-1)/k) 个道具。因此

前 i 关里被跳过的关数 <= floor((i-1)/k)     ... (*)

目标是最大化「被跳过的关的时间之和」，答案 = 总时间 - 该最大值。

这是经典的「前缀容量约束下选最大权子集」（拟阵上的贪心），用小根堆在线维护：从左往右扫 i，把 a_i 放进堆；容量 c_i = floor((i-1)/k) 是非减的，若堆的大小超过 c_i，就弹出堆里最小的那个。扫完后堆里剩下的就是最终要跳的关。

合法性：任一前缀 i 里被最终选中的元素，在第 i 步时都还在堆内，而那时堆大小 <= c_i，满足 (*)；
最优性：容量非减 + 每次只淘汰当前最小者，是标准的交换论证。

验算样例 2（n=6, k=2, a=[1,1,4,5,1,4]）：c = [0,0,1,1,2,2]。 i=1 推 1 又弹掉；i=2 同理；i=3 堆={4}；i=4 推 5 超容量弹 4，堆={5}； i=5 堆={1,5}；i=6 推 4 超容量弹 1，堆={4,5}。跳掉 9，总时间 16-9=7 ✓。

数据规模与复杂度¶

n,k <= 1e5，a_i <= 1e5。堆操作 O(n log n)，总和上界 1e10 需 long long（C++）。

坑在哪¶

跳关本身也算通过一关，所以计数器照常推进（样例 3 就是在考这个： k=1 时第一关打完之后，后面全能跳，答案只有 a_1 = 2）；
容量是 floor((i-1)/k) 而不是 floor(i/k)：进第 i 关时第 i 关还没通过，用 floor(i/k) 会多算一个道具，样例 1 就会错成 1 而不是 4；
道具可以攒着不用，也可以在任意后续关卡使用，所以只有前缀数量约束，没有「必须立刻用掉」的限制；
n = k 时 c_n = floor((n-1)/k) = 0，一个都跳不了；
heapq 只有小根堆，这里正好要淘汰最小值，无需取负号； heappushpop 是「先压再弹」的合并操作，比 heappush + heappop 少一次调整。

堆的用法见 35-优先队列与堆，反悔贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI49.py
import sys
from heapq import heappush, heappushpop


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = [int(v) for v in data[2:2 + n]]

    heap = []                       # 小根堆：当前决定跳过的关卡耗时
    total = 0
    for i in range(1, n + 1):       # i 用 1 基编号，与容量公式 (i-1)//k 对齐
        t = a[i - 1]
        total += t                  # 顺手累计总时间，省一次遍历
        cap = (i - 1) // k          # 进入第 i 关之前手上的道具总数
        if len(heap) < cap:
            heappush(heap, t)       # 还有空余道具，先收下再说
        elif cap and t > heap[0]:
            heappushpop(heap, t)    # 容量满了，换掉最小的那个
        # cap == 0（还没攒到道具）或 t <= 堆顶（换了反而更亏）时什么都不做
    print(total - sum(heap))        # 总时间减去被跳过的耗时之和


main()

BISHI49 小红闯关¶