小红闯关

思路

题目在说什么？有 个关卡，必须按顺序通过。通过第 关需要 时间。每通过 个关卡（无论是正常通过还是用道具跳过），就获得一个跳关道具。跳关道具可以在任意关卡使用，使用后零时间通过该关。问通过所有关卡的最少时间。

那怎么想这道题呢？

关键观察

首先，无论怎么选择跳哪些关卡，所有 关都会被通过（要么花时间打，要么用道具跳）。所以第 关（1-indexed）通过后，累计通过了 关，已获得 个道具。

但道具在通过第 关之后才产生，所以在第 关之前，可用的道具数量是 。

于是问题转化为：从 个关卡中选出一个子集 来跳过，最大化 （即省下的时间），同时对所有 都满足 。

答案就是 。

贪心策略

用一个小根堆维护当前选中要跳过的关卡的耗时。从左到右扫描每个关卡 ：

  • 如果当前选中的跳过数 < （即还有空余道具），直接把 加入堆。
  • 如果已经选满了，但 比堆中最小值更大，就把最小的换出来，把 放进去——这样总省时更多。

这样保证了在每个前缀处，跳过的关卡数都不超过该前缀允许的道具数。

时间复杂度 ，空间复杂度 。

代码

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

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

    priority_queue<int, vector<int>, greater<int>> minHeap;
    long long skippedSum = 0;

    for (int i = 0; i < n; i++) {
        int j = i + 1;
        int capacity = (j - 1) / k;

        if ((int)minHeap.size() < capacity) {
            minHeap.push(t[i]);
            skippedSum += t[i];
        } else if (capacity > 0 && !minHeap.empty() && t[i] > minHeap.top()) {
            skippedSum -= minHeap.top();
            minHeap.pop();
            minHeap.push(t[i]);
            skippedSum += t[i];
        }
    }

    printf("%lld\n", totalSum - skippedSum);
    return 0;
}

import java.util.*;

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

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        long skippedSum = 0;

        for (int i = 0; i < n; i++) {
            int j = i + 1;
            int capacity = (j - 1) / k;

            if (minHeap.size() < capacity) {
                minHeap.offer(t[i]);
                skippedSum += t[i];
            } else if (capacity > 0 && !minHeap.isEmpty() && t[i] > minHeap.peek()) {
                skippedSum -= minHeap.poll();
                minHeap.offer(t[i]);
                skippedSum += t[i];
            }
        }

        System.out.println(totalSum - skippedSum);
    }
}

import sys
import heapq
input = sys.stdin.readline

n, k = map(int, input().split())
t = list(map(int, input().split()))
total_sum = sum(t)

min_heap = []
skipped_sum = 0

for i in range(n):
    j = i + 1
    capacity = (j - 1) // k

    if len(min_heap) < capacity:
        heapq.heappush(min_heap, t[i])
        skipped_sum += t[i]
    elif capacity > 0 and min_heap and t[i] > min_heap[0]:
        skipped_sum -= heapq.heappop(min_heap)
        heapq.heappush(min_heap, t[i])
        skipped_sum += t[i]

print(total_sum - skipped_sum)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, k] = lines[0].split(' ').map(Number);
    const t = lines[1].split(' ').map(Number);
    let totalSum = 0;
    for (let i = 0; i < n; i++) totalSum += t[i];

    const heap = [];
    const heapPush = (v) => {
        heap.push(v);
        let i = heap.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (heap[p] <= heap[i]) break;
            [heap[p], heap[i]] = [heap[i], heap[p]];
            i = p;
        }
    };
    const heapPop = () => {
        const top = heap[0];
        const last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < heap.length && heap[l] < heap[s]) s = l;
                if (r < heap.length && heap[r] < heap[s]) s = r;
                if (s === i) break;
                [heap[s], heap[i]] = [heap[i], heap[s]];
                i = s;
            }
        }
        return top;
    };

    let skippedSum = 0;
    for (let i = 0; i < n; i++) {
        const j = i + 1;
        const capacity = Math.floor((j - 1) / k);

        if (heap.length < capacity) {
            heapPush(t[i]);
            skippedSum += t[i];
        } else if (capacity > 0 && heap.length > 0 && t[i] > heap[0]) {
            skippedSum -= heapPop();
            heapPush(t[i]);
            skippedSum += t[i];
        }
    }

    console.log(totalSum - skippedSum);
});