Boxers [Codeforces Round #579 (Div. 3) E]

https://codeforces.com/contest/1203/problem/E

N要素の配列Aがある。
各要素1だけ増減することができる（自然数の範囲で）とき、作ることのできる数の最大種類数は？
1≦N≦150000

解説

https://codeforces.com/contest/1203/submission/58867373

貪欲に作ることができそう。
例えば、1を作りたいときは、2を使ってるのがいい。
2を作りたいときは、1が使えるときはなるべく1を使ってやるほうがいい。3は4でも使えそう。
そのため、小さい数から貪欲に作れるかどうか試していき、作っていく。

int N, A[151010];
int cnt[151010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) cnt[A[i]]++;

    int ans = 0;
    rep(i, 1, 150002) {
        if (1 < i and 0 < cnt[i - 1]) ans++, cnt[i - 1]--;
        else if (0 < cnt[i]) ans++, cnt[i]--;
        else if (0 < cnt[i + 1]) ans++, cnt[i + 1]--;
    }
    cout << ans << endl; 
}