【思维构造】Element Extermination—CF1375C

Element Extermination—CF1375C
参考文章

思路

若 $a_1<a_n$，
初始时 $a_2,...,a_{n-1}$ 这 $n-2$ 个元素中大于 $a_1$ 中的元素都能通过 $a_1$ 而被删除，而小于 $a_n$ 中的元素都能通过 $a_n$ 而被删除。易知这样这 $n-2$ 个元素一定大于 $a_1$ 或小于 $a_n$，所以最后剩下初始时的 $a_1$ 和 $a_n$，任意删除其中一个即可。

若 $a_1>a_n$，
因为在删除 $a$ 中的元素的时候，易知 $a_1$ 不会减小，$a_n$ 不会增大。所以动态变化的数组 $a$ 无论什么时候都一定满足 $a_1>a_n$，那么显而易见 $a$ 数组不可能剩一个元素。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 3e5 + 10;

int n;
int a1, an;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> an;
		if (i == 1) {
			a1 = an;
		}
	}
	
	if (a1 < an) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35