問題
問題文
高橋君は，$N$ 個のボールを持っています． 最初，$i$ 番目のボールには，整数 $A_i$ が書かれています．
高橋君は，いくつかのボールに書かれている整数を書き換えて，$N$ 個のボールに書かれている整数が $K$ 種類以下になるようにしたいです．
高橋君は，少なくとも何個のボールの整数を書き換える必要があるでしょうか？
制約
・$1 \le K \le N \le 200000$
・$1 \le A_i \le N$
・与えられる数値はすべて整数
収録されている問題セット
回答
回答1 (AC)
どの番号のボールが何個あるかを調べる必要がありますが、今回の場合、番号は高々 $N \le 200000$ 種類なので、配列 number を用意し、number.at(i) で番号 i の個数を保持することにします。
求めたいのは番号を書き換えるボールの個数の最小値ですが、書き換える個数を最小にするには書き換えない個数を最大にする必要があります。そこで、配列 number を降順 (多い順) にソートしてボールの個数が多い最初の k 項を書き換えないことにすれば、その個数が最大となります。よって書き換えるボールの個数は k+1 項目から最後の項までの和となります。
ここまでの処理をまとめると以下のコードになりました。
abc081c-1.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for ( int i=0; i<n; i++ ) {
cin >> a.at(i);
}
vector<int> number(n,0);
for ( int i=0; i<n; i++ ) {
number.at(a.at(i)-1)++;
}
sort( number.rbegin(), number.rend() );
int sum = 0;
for ( int i=k; i<n; i++ ) {
sum += number.at(i);
}
cout << sum << endl;
}
上のコードは $N$ 回の繰り返しと $N$ 個の要素のソートを処理しているので、計算量は $O(M+N \log{N})=O(N \log{N})$ です。
調べたこと
AtCoder の解説 → ユーザ解説
回答1と同じ方針でした。
AtCoder の解説 → 公式解説
回答1と同じ方針でした。