当前位置： 移动技术网 > 移动技术>移动开发>Android > 【3】Codeforces Global Round 9. C. Element Extermination

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

2020年07月08日  | 移动技术网移动技术  | 我要评论

题目


题目

思路

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

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

所以我们要么

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

解法：
只需要比较a1a_1和ana_{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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网