小红闯关

[题目链接](https://www.nowcoder.com/practice/7ce4b75f7a304be481e73bc4dd2705a4)

思路

有 个关卡，通过第 个关卡需要 单位时间，必须按顺序通过。每通过 个关卡（包括用跳关道具跳过的关卡），获得一个跳关道具，使用后可以 时间通过任意一个关卡。求通过所有关卡的最少时间。

关键观察

无论哪些关卡被跳过，每个关卡都会被"通过"（要么花时间，要么用道具跳过），因此关卡的完成进度是固定的——通过前 个关卡后，总共获得 个跳关道具。

第 个道具在通过第 个关卡后获得，最早可用于第 个关卡。因此总共可以跳过 个关卡。

贪心策略

目标：从第 个关卡到第 个关卡中，选择若干关卡跳过，使得节省的时间最大。约束条件是：前 个关卡中，跳过的数量不能超过 （因为道具要先获得才能使用）。

使用从右往左扫描 + 最大堆的贪心方法：

  1. 从第 个关卡到第 个关卡，依次将 加入最大堆。
  2. 当扫描到位置 （），若 是 的倍数，说明道具 可以用于位置 及之后的所有关卡，此时可用道具数 。
  3. 只要有可用道具，就从堆中取出最大值，累计节省时间。

这样做的正确性在于：从右往左扫描时，堆中只包含位置 的关卡，而在位置 新增的道具恰好可以用于这些关卡，因此不会违反"道具必须先获得才能使用"的约束。

样例演示

以样例 2 为例：。

从右往左扫描：

位置 堆中元素 新增道具 弹出 累计节省
6 无 — 0
5 （） 4 4
4 无 — 4
3 （） 5 9
2 无 — 9
1 无 — 9

总时间 ，与答案一致。跳过的是第 （代价 ）和第 （代价 ）关卡。

复杂度分析

  • 时间复杂度：，每个元素最多入堆、出堆各一次。
  • 空间复杂度：，用于存储堆。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<long long> a(n);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        total += a[i];
    }

    priority_queue<long long> pq;
    long long savings = 0;
    int skips = 0;

    for (int m = n; m >= 1; m--) {
        pq.push(a[m - 1]);
        if (m >= 2 && (m - 1) % k == 0) {
            skips++;
        }
        while (skips > 0 && !pq.empty()) {
            savings += pq.top();
            pq.pop();
            skips--;
        }
    }

    printf("%lld\n", total - savings);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] a = new long[n];
        long total = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            total += a[i];
        }

        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
        long savings = 0;
        int skips = 0;

        for (int m = n; m >= 1; m--) {
            pq.offer(a[m - 1]);
            if (m >= 2 && (m - 1) % k == 0) {
                skips++;
            }
            while (skips > 0 && !pq.isEmpty()) {
                savings += pq.poll();
                skips--;
            }
        }

        System.out.println(total - savings);
    }
}