题目链接：https://codeforces.com/contest/1375/problem/C
给出一个大小为 $n$ 的排列 $a$，如果 $a_i < a_{i+1}$，则可以选择移去二者之一，判断排列最终能否只剩一个数。
考虑小于 $a_0$ 的所有的数，如果这些数都可以移去，那么剩余的数都大于 $a_0$，显然也都可以移去。
所以可以记录大于 $a_0$ 的每个数的位置，然后标记它们左端可以移除的数，最后判断小于 $a_0$ 的数是否都能移除即可。
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; int a[n] = {}; int pos[n] = {}; for (int i = 0; i < n; i++) { cin >> a[i]; --a[i]; pos[a[i]] = i; } bool can_remove[n] = {}; bool vis[n] = {}; for (int i = n - 1; i > a[0]; i--) { for (int j = pos[i] - 1; j >= 0 and !vis[j]; j--) { can_remove[a[j]] = true; vis[j] = true; } } bool ok = true; for (int i = 0; i < a[0]; i++) if (!can_remove[i]) ok = false; cout << (ok ? "YES" : "NO") << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
一个小于 $a_0$ 的数只有在最右端的时不能移除，所以判断 $a_0 < a_{n - 1}$ 即可。
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; int a[n] = {}; for (int i = 0; i < n; i++) cin >> a[i]; cout << (a[0] < a[n - 1] ? "YES" : "NO") << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
Codeforces Global Round 9 C. Element Extermination
原文：https://www.cnblogs.com/Kanoon/p/13258153.html