ARC086 C : Not so Diverse(300)
作成日：2017.12.12
最終更新日：2017.12.12
問題概要
$N$個のボールにはそれぞれ整数$A_i$が書かれている。
ボールに書かれている整数が$K$種類以下になるようにするために書き換える必要のある整数は少なくとも何個であるか求めよ。
制約
$1 \leq K \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq N$
考え方
整数が初めから$K$種類以下であれば答えは$0$である。
そうでない時は$K$種類になるまで種類を減らす必要がある。
書き換える個数を少なくするためには、整数のうちそれが書かれたボールが少ないものを選べば良い。
$K$種類を超える数の整数を選んだ後、選ばなかった整数のうちの一つに選んだものを書き換えれば条件を満たす。
ソースコード
マクロ等はこちら
const int MC = 200010;
int N,K;
int A[MC];
vector<int> V;
int main(){
cin >> N >> K;
repp(i,0,N) cin >> A[i];
sort(A,A+N);
int z = 1;
repp(i,1,N){
if(A[i-1] == A[i]) ++z;
else {
V.PB(z);
z = 1;
}
}
V.PB(z);
sort(V.begin(),V.end());
int ans = 0;
repp(i,0,V.size()-K){
ans += V[i];
}
cout << ans << endl;
return 0;
}
解法まとめ
まず$A$に現れる整数それぞれについて、それが書かれたボールの数$B_A$を数える。(9-18行)
そして小さいものから$K$を超える数だけ$B_A$を選んで足し合わせたものが答えである。(19-24行)