题目描述

前缀和  记录所有塔高度小于等于i的高度总和
分别枚举目标高度，将高度变为该目标高度需要的总的操作次数，取最小操作次数

算法1

C++ 代码

#include<iostream>
using namespace std;
const int N=200010;
const int M=10010;
int a[N];
int n,k;
int c[M],s[M],cnt[M];//统计不同高度的塔的数量
int main(){
    cin>>n>>k;
    int max_cnt=0,max_h=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c[a[i]]++;
        max_h=max(max_h,a[i]);//记录最大高度
        max_cnt=max(max_cnt,c[a[i]]);    
    }

    //对于<=i的所有塔的高度总和进行维护  s[i]
    for(int i=1;i<=max_h;i++){
        s[i]=s[i-1]+i*c[i];
        cnt[i]=cnt[i-1]+c[i];//对于高度小于等于i的塔的数量进行维护
    }

    if(max_cnt>=k){
        cout<<0<<endl;//已经不需要操作了
    }else{
        int res=1e9;
        //对于每一种塔高作为目标高度进行枚举
        for(int i=1;i<=max_h;i++){
            int left=cnt[i]*i-s[i];
            int right=s[max_h]-s[i-1]-i*(n-cnt[i]+c[i]);
            if(cnt[i]>=k){          //左边塔的数量大于k，并不需要将左边所有的塔全部都变为k  
                res=min(res,left-(cnt[i]-k));      
                //因为每次都是在最低塔进行一次操作，所以多出来的操作为cnt[i]-k  只需要操作一次的塔多操作的
            }
           if(n-cnt[i-1]>=k){
                res=min(res,right-(n-cnt[i-1]-k));
                //每次都是在最高塔进行操作，多出来的操作也是一次操作的次数n-cnt[i-1]-k
            }

                res=min(res,left+right-(n-k));

        }
        cout<<res<<endl;
    }

    return 0;
}