CF1375C Element Extermination 题解

· · 题解

当我们想不出如何才能判断答案为 \texttt{YES} 的时候，不妨从对立面想，看看什么时候答案为 \texttt{NO}。

结合题目中的规则，以及样例可以观察到，在数组变化的过程中，最左端的数的大小一定不会减小，最右端的数的大小一定不会增加。

证明：移除一个数的条件为 a_i < a_{i+1}，如果最左端的数我们不移除，那么很显然，最左端的数大小不变；如果我们移除了最左端的数，那么新的最左端的数就成了 a_{i+1}，比原来的 a_i 要大。最右端的数的变化情况同理。

所以如果 a_1 > a_n，不管怎么消除数，最后一定不能只剩下 1 个数。因为就算我们能消到只剩下最后两个数，根据上面证明的结论，这两个数是一定无法移除其中一个的。

接着进行猜想：如果 a_1 < a_n，那么答案为 \texttt{YES}。

接下来我们就要尝试想出一个策略，保证当 a_1 < a_n 时，我们一定能按照规则操作使得最后只剩下一个数。

这个策略是这样的：每次找到一个离 a_1 最近的一个数 a_x，满足 a_x > a_1，然后我们用这个 a_x 一路向 a_1 “推”，“挤”掉所有下标在 (1,x) 中的数 a_i，然后这个 a_x 就来到了 a_1 旁边，我们再把 a_x 移走。反复重复这个策略，最后成为 a_x 的一定是 a_n，最后数组只剩下了 a_1。

综上所述：

代码：

#include<cstdio>
const int maxn = 3e5 + 10;
int a[maxn];

void solve()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", a + i);
    puts(a[n] > a[1] ? "YES" : "NO");
    return;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
        solve();
    return 0;
}