题解 | 小红闯关 c#

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //c#写法，垃圾牛客的c#只支持到.net4，只能以注释形式把代码放这儿

        /*string[] inputs = Console.ReadLine().Split(' ');
        int.TryParse(inputs[0], out int n);
        int.TryParse(inputs[1], out int k);
        List<int> TimeCostOfEachGames = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
        //c#的优先队列是一个最小堆，所以我们传入我们的自定义比较器，使它成为一个最大堆
        PriorityQueue<long, long> pq = new PriorityQueue<long, long>(Comparer<long>.Create((a, b) => b.CompareTo(a)));

        long totalCost = 0;
        long savedTime = 0;
        long maxTime = TimeCostOfEachGames.Sum();
        if(k == 1)//如果每通过一关就能获得一个跳关道具，那么只需要通过一关，后面的每一关都可以直接跳过，最后总耗时就是第一关的耗时
        {
            totalCost = TimeCostOfEachGames[0];
        }
        else if(k >= n)//如果获得跳关道具所需的关卡数量大于等于总关卡数量
        {
            totalCost = maxTime;
        }
        else//如果获得跳关道具所需的关卡数量小于总关卡数量
        {
            //因为我们的目标是“最小化总时间”，所以每获得一个道具，都应该用它跳过当前所有未使用的关卡中最耗时的那个。
            //所以，我们不需要在获得道具的那一刻就决定跳过哪个关卡，而是可以“先记下来”，等看到后面更大的关卡时再用。
            //从后往前遍历
            for (int i = n-1; i > 0; i++)
            {
                //看看遍历到当前关卡能不能获得跳关道具
                if(i % k == 0)
                {
                    pq.Enqueue(TimeCostOfEachGames[i], TimeCostOfEachGames[i]);//将当前关卡的耗时加入优先队列
                    savedTime += pq.Dequeue();//将i到n-1之间最消耗时间的关卡的耗时加入savedTime，表示当前获得的跳关道具可以跳过的耗时
                }
                else
                {
                    pq.Enqueue(TimeCostOfEachGames[i], TimeCostOfEachGames[i]);//将当前关卡的耗时加入优先队列
                }

            }
        }

        totalCost = maxTime - savedTime;
        Console.WriteLine(totalCost); */
		
	  //java代码
        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);


    }
}