题目链接

小红闯关

题目描述

小红在玩一个游戏，这个游戏有 个关卡，通过第 个关卡需要消耗 个单位时间。小红必须按从前往后的顺序通过每一个关卡。

每当小红通过 个关卡（无论是付费通关还是使用道具），她都会获得一个跳关道具。跳关道具可以在任意一个关卡使用，使用后可以不消耗时间直接通过关卡。

小红想知道她通过这 个关卡，所需的最少时间是多少。

解题思路

这是一个贪心问题，可以通过优先队列（大顶堆）巧妙地解决。

我们的策略是从后往前遍历所有关卡。当我们从第 关遍历到第 关时，我们维护一个优先队列。这个队列里存放的是我们已经“路过”的所有关卡的耗时，这些关卡都是未来可以被跳过的候选对象。

根据题意，每通过 个关卡就会获得一个跳关道具。这个道具是在通过第 关、第 关、第 关……之后获得的。

核心贪心思路如下：

  1. 我们从第 关开始向前遍历到第 关。
  2. 在遍历到第 关时，我们首先将第 关的耗时 放入优先队列。
  3. 然后我们检查：如果小红在通过第 关后，累计通过的关卡数恰好是 的倍数，那么她就会获得一个跳关道具。在我们的逆向遍历模型中，这意味着当 是 的倍数时，一个跳关机会被“解锁”。
  4. 这个新获得的道具，应该被用在所有它能覆盖的关卡中（即第 关之后的所有关卡）耗时最长的那一关。由于我们的优先队列里已经存放了第 到 关的所有耗时，我们只需要取出队头元素（最大值），就是这个最优选择。
  5. 我们从总耗时中减去这个最大耗时。

通过这种从后往前的遍历方式，我们保证了每个跳关道具都被用在了能节省最多时间的关卡上，从而得到全局最优解。

代码

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

using namespace std;
using LL = long long;

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

    priority_queue<LL> pq;
    LL saved_time = 0;

    // 从后往前遍历
    for (int i = n - 1; i >= 0; --i) {
        // 当我们处理完第 i 关时（0-indexed），
        // 如果 i+1 是 k 的倍数, 说明在通过这一关后,
        // 小红获得了一个跳关道具。
        // 注意：道具是在检查之后才放入队列，所以可以用在未来的关卡上
        if ((i + 1) % k == 0 && !pq.empty()) {
            // 这个道具应该用在已遍历过的关卡（i+1 到 n）中耗时最长的那个
            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 total_time = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            total_time += a[i];
        }

        // 大顶堆
        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
        long saved_time = 0;

        // 从后往前遍历
        for (int i = n - 1; i >= 0; i--) {
            // 如果 i+1 是 k 的倍数, 说明在通过这一关后获得了一个跳关道具
            if ((i + 1) % k == 0 && !pq.isEmpty()) {
                // 用在已遍历过的关卡（i+1 到 n）中耗时最长的那个
                saved_time += pq.peek();
                pq.poll();
            }
            // 将当前关卡的耗时加入优先队列
            pq.add(a[i]);
        }

        System.out.println(total_time - saved_time);
    }
}

import heapq

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

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

    # 从后往前遍历
    for i in range(n - 1, -1, -1):
        # 如果 i+1 是 k 的倍数,获得跳关道具
        if (i + 1) % k == 0 and pq:
            # 取出耗时最长的关卡(绝对值最大的负数)
            saved_time += -heapq.heappop(pq)
        
        # 将当前关卡的耗时(的负数)加入堆
        heapq.heappush(pq, -a[i])

    print(total_time - saved_time)

solve()

算法及复杂度

  • 算法：贪心、优先队列
  • 时间复杂度：，其中 是关卡数量。我们需要遍历所有关卡，每次遍历都可能对优先队列进行一次操作（push），单次操作的复杂度是 ，其中 是队列大小。在最坏情况下， 接近 。
  • 空间复杂度：，在最坏情况下，优先队列需要存储所有关卡的耗时。