题解 | 小红闯关-Java

import java.util.*;

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

        int[] times = new int[n];
        for (int i = 0; i < n; i++) {
            times[i] = scanner.nextInt();
        }

        // 计算能获得的跳关道具数量
        int props = n / k;

        // 如果没有道具，直接返回所有关卡时间总和
        if (props == 0) {
            long sum = 0;
            for (int time : times) {
                sum += time;
            }
            System.out.println(sum);
            return;
        }

        // 使用小顶堆来保存我们要跳过的最大时间关卡
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        long totalSum = 0;

        for (int i = 0; i < n; i++) {
            totalSum += times[i];

            // 记录当前已获得的道具数量 (到第i+1关为止)
            int currentProps = i / k;

            // 如果当前已获得的道具数量多于堆的大小，说明刚获得了新道具
            if (currentProps > minHeap.size()) {
                minHeap.add(times[i]);
            }
            // 如果已经获得了道具，且当前关卡时间比堆中最小的要大，则替换
            else if (currentProps > 0 && times[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.add(times[i]);
            }
        }

        // 计算需要减去的总时间（被跳过的关卡）
        long skipSum = 0;
        while (!minHeap.isEmpty()) {
            skipSum += minHeap.poll();
        }

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