ARC087 C : Good Sequence(300)
作成日：2017.12.17
最終更新日：2017.12.17
問題概要
良い数列とは、数列の各要素$x$が数列中にちょうど$x$個あるような数列である。
長さ$N$の正整数からなる数列$\{a\}$からいくつかの要素を取り除いて数列$\{a\}$を良い数列にしたい。
取り除くべき要素の個数の最小値を求めよ。
制約
$1 \leq N \leq 10^5$
$1 \leq a_i \leq 10^9$
考え方
数列中に要素$x$が$y$個あったとする。
条件を満たすには$y = 0$または$y = x$にしなければならない。
取り除く要素を最小にしたいから、$y \geq x$の時は$(y-x)$個、そうでない時は$y$個取り除くのが最善である。
ソースコード
マクロ等はこちら
int N;
int a[100010];
int main(){
cin >> N;
repp(i,0,N) cin >> a[i];
sort(a,a+N);
int ans = 0;
int z = 1;
repp(i,0,N){
if(a[i] == a[i+1]) ++z;
else {
if(z < a[i]) ans += z;
else ans += z-a[i];
z = 1;
}
}
cout << ans << endl;
return 0;
}解法まとめ
数列に現れる整数$x$それぞれについて登場する回数$z$を求め、$z < x$の時$z$個、そうでない時$(z-x)$個要素$x$を消すことにする。(7-18行)