题解 | 小红闯关

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.Collections;


public class Main {
    public static void main(String[] args) throws IOException {
        // 替换Scanner为BufferedReader，提升大数据量下的输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 替换System.out.println为PrintWriter，提升输出效率
        PrintWriter out = new PrintWriter(System.out);
        
        // 读取第一行的n和k（使用split分割空格，替代StringTokenizer）
        String[] firstLine = br.readLine().split("\\s+"); // \\s+匹配任意空白符（空格/制表符等）
        int n = Integer.parseInt(firstLine[0]); // 关卡数量
        int k = Integer.parseInt(firstLine[1]); // 获得道具的关卡数条件
        
        // 存储每个关卡的耗时（用long避免数值溢出）
        long[] timePerLevel = new long[n];
        long totalTime = 0; // 不使用任何道具时的总耗时
        
        // 读取第二行的关卡耗时数组（split分割）
        String[] timeStrArray = br.readLine().split("\\s+");
        for (int i = 0; i < n; i++) {
            timePerLevel[i] = Long.parseLong(timeStrArray[i]);
            totalTime += timePerLevel[i]; // 累加总耗时
        }
        
        // 初始化最大堆（优先队列），用于存储可跳过的关卡耗时（优先弹出最大值）
        // PriorityQueue默认是最小堆，Collections.reverseOrder()转为最大堆
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        long savedTime = 0; // 累计跳过的关卡总耗时（跳过越多，总耗时越少）
        
        // 核心逻辑：从后往前遍历关卡（i从最后一关到第一关）
        for (int i = n - 1; i >= 0; i--) {
            // (i+1)表示"已通过前i+1个关卡"（按顺序），满足每k个关卡则获得1个道具
            // 0-based索引转1-based计数，确保规则匹配
            if ((i + 1) % k == 0 && !maxHeap.isEmpty()) {
                // 获得道具，跳过堆中耗时最大的关卡，累加跳过的耗时
                savedTime += maxHeap.poll();
            }
            // 将当前关卡加入堆，作为"可跳过"的候选（未来通关时可使用道具跳过）
            maxHeap.add(timePerLevel[i]);
        }
        
        // 最小总耗时 = 全通关耗时 - 跳过的最大耗时之和
        out.println(totalTime - savedTime);
        
        // 刷新并关闭输出流，确保数据全部输出（必须执行flush，避免数据丢失）
        out.flush();
        out.close();
        br.close();
    }
}