题解 | #小红闯关#

题目链接

题目描述

小红需要按顺序通过 $n$ 个关卡。通过第 $i$ 个关卡需要花费 $a_i$ 的时间。每当小红通过了 $k$ 个关卡（无论是花费时间还是使用道具），她都会获得一个“跳关道具”。跳关道具可以用于任何一个关卡，使用后能以 0 时间通过该关卡。请计算通过所有 $n$ 个关卡所需的最少总时间。

解题思路

这是一个经典的优化问题，但其决策具有时间上的依赖性，直接从前往后贪心容易出错。一个非常巧妙的解法是从后往前进行动态规划和贪心选择。

核心思想：从后往前遍历，利用对“未来”的认知

当我们从后往前（i 从 n-1 到 0）遍历关卡时，在任意一个位置 i，我们都已经知道了它之后所有关卡（i+1 到 n-1）的耗时情况。这为我们的贪心决策提供了完美的信息。

道具的使用时机：在真实的游戏中，小红在通过第 i 关（0-indexed, 即第 i+1 关）后，如果满足条件，会获得一个道具。这个道具可以用在之后的任意关卡。
从后往前的视角：当我们从后往前遍历时，在 i 处，我们维护一个“待选池”，里面存放了从 i+1 到 n-1 所有关卡的耗时。一个最大堆（Max-Heap）是维护这个“待选池”并随时取出最大值的理想工具。
- 当我们处理到第 i 关时，如果 (i+1) % k == 0，这意味着在真实游戏中，小红在这一关结束后会获得一个道具。她应该用这个道具跳过哪个关卡呢？显然是她未来会遇到的、最耗时的那个。
- 在我们从后往前的视角里，这个“未来”就是我们已经遍历过、并放入最大堆里的那些关卡（i+1 到 n-1）。
- 因此，我们就在此刻，从最大堆中取出最大值，决定“跳过”它。

算法步骤

首先计算出总耗时 total_time，假设所有关卡都需要付费。
创建一个最大堆 pq 和一个 saved_time 变量。
从后往前遍历关卡（i 从 n-1 到 0）： a. 检查道具：首先检查在通过 i 关后是否获得道具，即 (i+1) % k == 0。 b. 如果是，并且 pq（代表着 i+1 到 n-1 关）不为空，我们就从 pq 中取出最大值，累加到 saved_time 中，并从 pq 中移除它。这代表我们用这个新获得的道具，跳过了未来的一个最耗时的关卡。 c. 更新待选池：将当前关卡的耗时 a[i] 压入最大堆 pq。这样，当 i 前进到 i-1 时，pq 就代表了 i 到 n-1 的所有关卡，为下一次决策做好了准备。
最终答案就是 total_time - saved_time。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    long long total_time = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total_time += a[i];
    }

    priority_queue<long long> pq; // 最大堆
    long long saved_time = 0;

    // 从后往前遍历
    for (int i = n - 1; i >= 0; --i) {
        // 检查在通过此关后是否获得道具
        // 如果是，用它跳过未来（i+1 到 n-1）最耗时的关卡
        if ((i + 1) % k == 0 && !pq.empty()) {
            saved_time += pq.top();
            pq.pop();
        }
        // 将当前关卡加入“未来”的候选池
        pq.push(a[i]);
    }

    cout << total_time - saved_time << endl;

    return 0;
}

import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        long[] a = new long[n];
        long totalTime = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            totalTime += a[i];
        }
        
        // Java的PriorityQueue默认是最小堆，需要提供比较器实现最大堆
        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
        long savedTime = 0;

        // 从后往前遍历
        for (int i = n - 1; i >= 0; i--) {
            // 检查在通过此关后是否获得道具
            if ((i + 1) % k == 0 && !pq.isEmpty()) {
                // 用它跳过未来（i+1 到 n-1）最耗时的关卡
                savedTime += pq.poll();
            }
            // 将当前关卡加入“未来”的候选池
            pq.add(a[i]);
        }

        System.out.println(totalTime - savedTime);
    }
}

import sys
import heapq

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    total_time = sum(a)
    
    # Python的heapq是最小堆，我们存入负数来模拟最大堆
    pq = [] 
    saved_time = 0

    # 从后往前遍历
    for i in range(n - 1, -1, -1):
        # 检查在通过此关后是否获得道具
        if (i + 1) % k == 0 and pq:
            # 用它跳过未来（i+1 到 n-1）最耗时的关卡
            max_cost = -heapq.heappop(pq)
            saved_time += max_cost
        
        # 将当前关卡加入“未来”的候选池
        heapq.heappush(pq, -a[i])
    
    print(total_time - saved_time)

solve()

算法及复杂度

算法：贪心
时间复杂度：我们需要遍历所有 $n$ 个关卡。在每一步中，我们对优先队列（堆）进行一次插入和可能的提取操作，其时间复杂度为 $\mathcal{O}(\log n)$ 。因此，总的时间复杂度为 $\mathcal{O}(n \log n)$ 。
空间复杂度：优先队列最多会存储 $n$ 个关卡的耗时，因此空间复杂度为 $\mathcal{O}(n)$ 。