题解 | 小红闯关

这一题如果正着求就会出现不知道什么时候使用跳关卡最好的情况

应当倒着求，我们要把a[i]装入优先队列中，并且每当i%k==0时，就要把队列中最大的那个出队，这样就能保证，每一张跳关卡都用在刀刃上，不会浪费

我们使用优先队列来保证装入的元素始终保持从大到小的顺序

当然要注意，由于n和a[i]的范围都是10e5，所以时有可能超过int范围的，比如n个a[i]都装进count中,所以要开long

对于优先队列，默认是从小到大排序，要想让它变成从大到小，应当使用Collections.reverseOrder()

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		这一题得倒着求，这样才能利益最大化，正着求根本不知道什么时候是最大利益的
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int k=scanner.nextInt();
		long a[]=new long[n];
		long count=0;
		for (int i = 0; i < a.length; i++) {
			a[i]=scanner.nextLong();
			count+=a[i];
		}
//		创建一个从大到小排序的优先队列
		PriorityQueue<Long> queue=new PriorityQueue<>(Collections.reverseOrder());
		for (int i = a.length-1; i >=k; i--) {
			queue.offer(a[i]);
			if(i%k==0) {
				count-=queue.poll();
			}
			
		}
		System.out.println(count);

	}

}