【Codeforces Global Round 9 C】Element Extermination
Codeforces Element round global
2023-09-14 09:03:41 时间
题目链接
翻译
给你一个排列,你每次可以将 \(a[i]<a[i+1]\) 中的 \(a[i]\) 或者 \(a[i+1]\) 删掉。
问你,最后能不能删得只剩下 \(1\) 个元素。
题解
考虑最大的元素 \(n\), 想想它是不是能一直往左删元素?
但是删到第一个元素的时候,就不能再删了,因为 \(n\) 可能不是最后一个元素,如果再删的话,就没有
其他元素能删掉 \(n\) 了, 没办法这个时候只能保留第一个元素然后把 \(n\) 给删掉了。
然后接着找 \(n\) 右边的次大的元素 \(x\) (\(n\) 左边只剩第一个数字了),也重复进行删除元素操作。
如果 \(x\) 不是最右边那个元素的话,仍然不能删掉第一个元素... 依次类推
不难发现,只要排列的最后一个元素是大于第一个元素的,那么最后一定能轮到这个 \(a[n]\) 进行这样的
步骤,就能删掉第一个元素,只剩一个元素 \(a[n]\) 啦。
如果最后一个元素小于第一个元素,根据上面的过程可以发现,第一个元素没办法被删除。
神奇的一道题。
代码
#include <cstdio>
using namespace std;
const int N = 3e5;
int T, n;
int a[N + 10];
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i = 1;i <= n; i++){
int x;
scanf("%d",&a[i]);
}
if (a[n] > a[1]){
puts("YES");
}else{
puts("NO");
}
}
return 0;
}
相关文章
- codeforces A. Bayan Bus(简单模拟)
- 【Codeforces Round #223 (Div. 1) C】Sereja and Brackets
- 【Codeforces Round #446 (Div. 2) A】Greed
- 【42.86%】【codeforces 742D】Arpa's weak amphitheater and Mehrdad's valuable Hoses
- 【39.66%】【codeforces 740C】Alyona and mex
- 【codeforces 787C】Berzerk
- 【codeforces 785C】Anton and Fairy Tale
- 【codeforces 548C】Mike and Frog
- 【codeforces 801B】Valued Keys
- 【codeforces 514D】R2D2 and Droid Army
- 【Codeforces Round #427 (Div. 2) A】Key races
- 【codeforces 731D】80-th Level Archeology
- 【codeforces 727D】T-shirts Distribution
- Codeforces 544E Remembering Strings 状压dp
- Codeforces Round #274 (Div. 2)
- Codeforces Round #265 (Div. 2) C. No to Palindromes! 构建无回文串子
- CodeForces Hello 2023 B