【Codeforces Global Round 9 C】Element Extermination

题目链接

点我呀

翻译

给你一个排列，你每次可以将 (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;
}