Good Sequence [AtCoder Regular Contest 087 C]

解法

https://beta.atcoder.jp/contests/arc087/submissions/1874156

数の種類ごとに数えておこう。
数xの個数が…

• ピッタリx個なら、何もしなくてもいい
• x個未満なら、全て消してしまう必要がある
• x個より大きいなら、x個に揃えるように消す

となるので、数の個数毎に必要な最小個数を調べて総和を答える。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    map<int, int> cnt;
    rep(i, 0, N) cnt[A[i]]++;
 
    int ans = 0;
    fore(p, cnt) {
        if (p.first == p.second) continue;
        if (p.first < p.second) ans += p.second - p.first;
        else ans += p.second;
    }
    cout << ans << endl;
}