欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

【3】Codeforces Global Round 9. C. Element Extermination

程序员文章站 2022-06-15 12:38:34
题目http://codeforces.com/contest/1375/problem/C思路由于满足aia2a_1 > a_2a1​&...

题目

http://codeforces.com/contest/1375/problem/C
【3】Codeforces Global Round 9. C. Element Extermination

思路

由于满足ai<ai+1a_i < a_{i+1}的序列才能被消除,所以我们尽可能让前面的数字更小。

从左往右依次考虑每一个数字。
假如a1<a2a_1 < a_2,则保留a1a_1,于是变成a1a_1a3a_3的比较,和a1a_1a2a_2的比较同理。
假如a1>a2a_1 > a_2,则一直往后,找到第一个满足ak>a1a_k > a_1的数。由于a2,...,ak1a_2, ..., a_{k-1}之间的数都比aka_k要小(因为ak>a1>a2a_k > a_1 > a_2aka_k是第一个比a1a_1大的),则从aka_k开始从右往前比较,并且总是保留aka_k,最后就变成a1a_1aka_k的比较。由于已经知道ak>a1a_k > a_1,所以保留a1a_1,变成a1a_1ak+1a_{k+1}的比较,和a1a_1a2a_2的比较同理。假如没有找到满足要求的aka_k,即a1a_1大于它之后的所有数,则最后无法消除。

所以我们要么

  • 直到最后一个元素发现a1>ana_1 > a_{n},也找不到aka_k。于是答案NO。
  • 找到满足条件的aka_k,把a2a_2aka_k的元素全部消除。消除到最后,变成a1a_1ana_{n}的比较。所以我们发现,只要最后一个数ana_{n}大于a1a_1,则我们总可以消除到只有一个元素。

解法:
只需要比较a1a_1ana_{n}的大小。如果a1>ana_1 > a_{n},则NO,否则YES。

note: 这里把数组画在坐标系上会更容易理解。

代码

代码均为提交通过版本。为保持比赛时原样,没有后期优化或者修改。但为方便阅读,可能会增加注释。

#include <iostream>
using namespace std;
 
int main() {
	int tcase;
	std::ios::sync_with_stdio(false);
	cin >> tcase;
	while(tcase--) {
		int n;
		cin >> n;
		int first, last;
		for(int i = 0; i < n; i++) {
			int x;
			cin >> x;
			if (i == 0) {
				first = x;
			} else if (i == n - 1) {
				last = x;
			}
		}
		if (first < last) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

本文地址:https://blog.csdn.net/rbb317/article/details/107138373