修塔游戏题解

贪心的思想，同时其他答案里给的bug测试用例也可以通过

package acm;

import java.util.*;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        int sum=0;
        int[] data=new int[n];
        for(int i=0;i<n;i++){
            data[i]=sc.nextInt();
            sum+=data[i];
        }
        Arrays.sort(data);
        int p=-1;
        int ans=Integer.MAX_VALUE;
        int pre=0;
        //最终的结果肯定是要有某个数出现的个数>=k，把这个数叫做基准数
        for(int i=0;i<n;){
            p=i;
            while(p<n&&data[p]==data[i]){
                sum-=data[i];
                p++;
            }
            int ned=Math.max(0,k-p+i);
            //ned的含义是目前如果让data[i]作为基准数，还差多少个达到k，如果为0说明已经超过k个了，也就是说不需要任何操作就可以满足题意要求
            if(ned==0){
                ans=0;
//                break;
            }
            if(p>=k){//p>=k说明以data[i]为基准数，调整下标i之前的数到达基准数，就可以满足题意，求出这时候需要操作个数
                ans=Math.min(ans,i*data[i]-pre-(i-ned));//pre记录的是下标i之前的所有数字之和，要把下标i之前的数调整到等于基准数data[i]，操作次数=i*data[i]-pre
                //同时要考虑只需要k个满足就可以了，也就是这时候可以有i-ned不满足，也就是i-ned个数可以调整等于data[i]-1，所以要减去i-ned.
            }
            if(n-i>=k){//i往后的数字降到data[i]就直接可以满足题意，与p>=k类似，只是调整方向不一样
                ans=Math.min(ans,sum-(n-p)*data[i]-(n-p-ned));//
            }
            ans=Math.min(ans,i*data[i]-pre+sum-(n-p)*data[i]-(n-(p-i)-ned));//同时需要判断两边都做操作的情况下调整的个数
            pre+=data[i]*(p-i);//pre加上data[i]乘以data[i]的个数，那么下一步i=p的时候pre就代表i之前所有数之和。
            i=p;
        }
        System.out.println(ans);
    }

}