AtCoder ABC 082 C - Good Sequence (5Q, 茶色, 300 点)

連想配列の良い練習問題！

• 問題へのリンク

問題概要

正の整数からなる数列が良い数列であるとは、数列に含まれる任意の整数値 について、数列中に がちょうど 個含まれていることをいう。

与えられた数列 に対して、いくつかの要素を削除することで、よい数列となるようにしたい。削除すべき要素数の最小値を求めよ。

制約

• 
• 

考えたこと

数列の数の並びは全く関係なくて、「どの数値が何個あるか」だけが重要。なので、まずは集計処理をしよう。次のような連想配列 (C++ ならば map 型) を構築する。

---

• nums[v]：数列 に含まれる整数値 の個数

---

そうしたあとは、値 ごとに考えていこう。次のようにすればよい。（答えを表す変数を res とする)

• nums[v] >= v のとき：値 を nums[v] - v 個削除すれば、数列中に が 個含まれる状態になる
  • つまり、res += nums[v] - v とする
• nums[v] < v のとき：この場合は値 をすべて削除するしかない
  • つまり、res += nums[v] とする

この解法の計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, a;
    cin >> N;
    map<long long, long long> nums;
    for (int i = 0; i < N; i++) {
        cin >> a;
        nums[a]++;
    }

    long long res = 0;
    for (auto [val, num] : nums) {
        if (num < val) res += num;
        else res += (num - val);
    }
    cout << res << endl;
}