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行)

ARC087の他の問題 D E F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら