CF Round #661 A - Remove Smallest


Tags:cpcodeforcesdiv3greedy

問題

https://codeforces.com/contest/1399/problem/A

問題文

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

制約

  • 1t10001 \le t \le 1000
  • 1n501 \le n \le 50
  • 1ai1001 \le a_i \le 100

サンプル

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;
  }
}