CF1637A

wzy2021 · 2022-02-13 12:34:26 · 题解

若有序，必须单增。

设前 i 个的最大值为 pre_i，后 i 个的最小值为 suf_i，

若要使得有序，满足操作后 a_{len} 与 a_{len+1} 有序，即 a_{len} < a_{len+1}，

而操作后，a_{len} 是前 len 的最大值，a_{len + 1} 是后 n - len 的最小值，

所以 pre_{len} \le suf_{len + 1}，

总结一下，得到：若能有序，则肯定存在 len 使得前 len 个的最大值小于后 n - len 的最小值。

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e4 + 10;
int a[maxn];
int pre[maxn], suf[maxn];

int main() {
    int T; scanf ("%d", &T);
    while (T --) {
        int n; scanf ("%d", &n);
        for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]);
        suf[n + 1] = 0x3f3f3f3f; // 一定要付为无穷大！！！
        for (int i = 1; i <= n; ++i) pre[i] = max (pre[i - 1], a[i]);
        for (int i = n; i >= 1; --i) suf[i] = min (suf[i + 1], a[i]);
        int flag = 0;
        for (int i = 0; i <= n; ++i) {
            if (pre[i - 1] > suf[i]) { // 上面的式子反过来，就是无序了
                flag = 1; break;
            }
        }
        if (flag) printf ("YES\n");
        else printf ("NO\n");
    }
    return 0;
}

这方法虽然不太好，但我觉得我想到的还挺妙的，所以写一篇题解记录一下。