题解 | 小红的数组清空

首先创造一个序列a,然后用哈希，在输入每一个a[i]的同时将对应的值得数量++，之后判断是否对x有x-1的这一项，如果有我们还需要判断每项的数量如果x的数量比x-1的数量少，则删除x无需代价,否则需要cnt[x]-cnt[x-1]代价。

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    unordered_map<int,int>cnt;
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    long long ans=0;
    for(auto&[x,num]:cnt){
       int t=cnt.count(x-1)?cnt[x-1]:0;
       ans+=num-min(num,t);
    }
    cout<<ans;
    return 0;
}