AtCoder Beginner Contest 082 C - Good Sequence
考察
配列に登場する数が数字より少なければその数字はすべて取り除く。
多ければ、多い分だけの差分を取り除けば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; }
配列で数字をカウントするのは良く出てくるので便利。