CF27C

FiraCode · 2022-10-01 18:36:42 · 题解

题意：

现在，给定一个 n 个整数的序列 a_1,a_2,...,a_n。

请你找到该序列的最短非有序子序列。

题解思路：

若他是非有序，那么就是有两种请况：

1. 先上升，再下降
2. 先下降，再上升

为什么没有相同的呢？

因为我们要求的是最短的子序列，所以有相等的我们只留一个就可以了。

而且我们发现这两种情况只需要三个元素就够了。

那么我们其实就是要求在这个序列里是否有三个元素满足：

第一个和第三个都大于或都小于中间的元素。

那么对于第一种情况，我们可以枚举中间的元素，那么我们只要判断是否有两个元素，满足一个在他左边一个在他右边并且两个数都比他小。

对于第二种请况同理，只是要求两边的元素都比他大就可以了。

那么我们就预处理 minn1_i,minn2_i,maxn1_i,maxn2_i 分别代表他前 i 个的最小值的下标，后 i 个的最小值的下标，前 i 个的最大值的下标和后 i 个的最大值的下标。

那么对于一个数，我们就判断他前面和后面的最大（最小）值是否满足条件即可。

CODE：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int minn1[100010], maxn1[100010], minn2[100010], maxn2[100010];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    if (n < 3) {//长度小于三就一定不行
        puts("0");
        return 0;
    }
    maxn1[1] = minn1[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[maxn1[i - 1]] > a[i])//若他是比前一个小，那么下标还是前i-1的最大值
            maxn1[i] = maxn1[i - 1];
        else
            maxn1[i] = i;//否则赋值成他自己
        if (a[minn1[i - 1]] < a[i])//最小值同理
            minn1[i] = minn1[i - 1];
        else
            minn1[i] = i;
    }
    //从后面开始的同理
    maxn2[n] = minn2[n] = n;
    for (int i = n - 1; i >= 1; --i) {
        if (a[maxn2[i + 1]] > a[i])
            maxn2[i] = maxn2[i + 1];
        else
            maxn2[i] = i;
        if (a[minn2[i + 1]] < a[i])
            minn2[i] = minn2[i + 1];
        else
            minn2[i] = i;
    }
    int i;
    for (i = 2; i < n; ++i) {//枚举中间值
        if(a[minn1[i - 1]] < a[i] && a[minn2[i + 1]] < a[i]) {//第一种情况
            puts("3");
            printf("%d %d %d\n", minn1[i - 1], i, minn2[i + 1]);
            break;
        }
        if (a[maxn1[i - 1]] > a[i] && a[maxn2[i + 1]] > a[i]) {//第二种请况
            puts("3");
            printf("%d %d %d\n", maxn1[i - 1], i, maxn2[i + 1]);
            break;
        }
    }
    if (i == n) {
        puts("0");
    }
    return 0;
}