https://beta.atcoder.jp/contests/arc086/tasks/arc086_a
解法
https://beta.atcoder.jp/contests/arc086/submissions/1858142
貪欲法をする。
違う数字に書き換える数はなるべく個数が少ない物を選んでいけばいい。
なので、数を種類ごとにカウントする。
次に貪欲法をやるために個数を抜き出して昇順ソートする(配列v)。
数の種類が元々K以下であれば、0を返す。
そうでないなら、n-K個だけ種類を減らす必要があるので、配列vからn-K個取り出した総和が答え。
int N, K, A[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; rep(i, 0, N) cin >> A[i]; // カウント map<int, int> cnt; rep(i, 0, N) cnt[A[i]]++; // 個数を抜き出して昇順ソート vector<int> v; fore(p, cnt) v.push_back(p.second); sort(v.begin(), v.end()); int n = v.size(); if (n <= K) { printf("0\n"); } else { int ans = 0; rep(i, 0, n - K) ans += v[i]; printf("%d\n", ans); } }