ぐってぃのプログラミング日記

競技プログラミングやIT関係の記事を書いていくよ

AtCoder Beginner Contest 082 C - Good Sequence

問題
beta.atcoder.jp


考察
配列に登場する数が数字より少なければその数字はすべて取り除く。
多ければ、多い分だけの差分を取り除けばOK。
配列の大きさは100000までなのでそれ以上の数字は配列に入れる前に取り除かれることが確定している。

実装

#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long

int cnt[100010] = {};
int main()
{
	int n;
	ll ans = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		if (a > 100000) {
			ans++;
		}
		else {
			cnt[a]++;
		}
	}

	for (int i = 1; i <= 100000; i++)
	{
		if (i == cnt[i] || cnt[i] == 0) {
			continue;
		}
		else if (cnt[i] < i) {
			ans += cnt[i];
		}
		else if (i < cnt[i]) {
			ans += cnt[i] - i;
		}
	}

	cout << ans << endl;
	return 0;
}

配列で数字をカウントするのは良く出てくるので便利。