题解：P16460 [UOI 2026] Minimum Deletion

· · 题解

题目传送门

P16460 [UOI 2026] Minimum Deletion

题意

给定一个包含 n 个从 0 到 9 的非负整数的数组 a，求最少需要多少次删除操作，才能使得操作后数组中最小的未出现的非负整数不超过 k。

每次只能删除一个数。

分析

既然这题求最小的删除次数使得操作后数组中最小的未出现的非负整数不超过 k，那么我们只需要看小于 k 的数的出现次数，在找到出现次数中的最小值即可。

原理很简单，若 k 以内最小出现次数为 w，那么我们只需要删除这 w 个数，就能使删去后数组最小未出现的非负整数不超过 k。

如果有一个数满足没有在原数组中出现且不超过 k，那么就不用删一个数，因为原数组就满足条件。

代码

仅供参考，其实 b 数组不用开很大，因为题目中数组的每个元素都是一位数。

最后要注意求最小值变量要初始化到极大值。

#include<bits/stdc++.h>
using namespace std;
long long n,a,k,b[100001],mina=1e9+10;
int main(){

    cin>>n>>k;
    for(long long i=0;i<n;i++){
        cin>>a;
        if(a>k){
            continue;
        }
        b[a]++;  // 统计次数
    }
    if(k==0){
        cout<<b[0];
        return 0;
    }
    for(long long i=0;i<=k;i++){  // 打擂台比较
        mina = min(mina,b[i]);
    }
    cout<<mina;

    return 0;
}

严禁抄袭。

管理员辛苦！