A - Remove Smallest

cpcodeforcesdiv3greedy

最終更新日

Table of Contents

Loading...

問題

https://codeforces.com/contest/1399/problem/A (新しいタブで開く)

問題文

iji \ne j となる i,ji, j を選び、 aiaj1|a_i - a_j| \le 1 なら小さいほうを削除する操作を繰り返す。
最終的に要素数を 11 にできるか?

制約

サンプル

5 3 1 2 2 4 5 5 5 5 3 1 2 4 4 1 3 4 4 1 100
YES YES NO NO YES

考察

nn が小さめなので、ソートしてから普通にシミュレーションしていい。
ソートすると、消せるなら前から消していくのが明らかに最適。

コード

https://codeforces.com/contest/1399/submission/126143386 (新しいタブで開く)

void solve() { int n; cin >> n; vector<int> a(n); rep(i, n) cin >> a[i]; sort(a.begin(), a.end()); int i = 0; while (i + 1 < a.size()) { if (a[i + 1] - a[i] <= 1) { a.erase(a.begin() + i); } else { i++; } } if (a.size() == 1) { cout << "YES" << endl; } else { cout << "NO" << endl; } }