题解：P15705 [2018 KAIST RUN Spring] Zigzag

· · 题解

蒟蒻的第一篇题解。

读题

给定一个长度为 N 的序列 A，你需要找出 A 的一个最长子段，该子段本身是一个 Zigzag 序列，即对于所有 i（1 \leq i \leq N - 2），既不满足 A_i \leq A_{i+1} \leq A_{i+2}，也不满足 A_i \geq A_{i+1} \geq A_{i+2}。

思路

不难注意到，这道题的数据范围并不大，只有 3\le N\le 5000，预计的时间复杂度为 O(n^2)。所以我们可以直接枚举所有情况。

想要三个数单调， 数列数必然要大于三个，所以我们忽略前两个，从第三个开始枚举即可。

具体内容看代码注释吧！

AC代码

#include<bits/stdc++.h>
#define f(i,a,b) for(int i=a; i<b; i++)
// 简化代码
using namespace std;
int a[5005];
int main(){
    int n, maxn = 2, step = 0;
    cin >> n;
    f(i,0,n) cin >> a[i];
    // 遍历所有可能的起始位置
    f(i,2,n){
        int j = i;
        // 从位置i开始，向后扩展，检查是否仍满足Zigzag条件
        while( j < n && !(( a[j] <= a[j-1] && a[j-1] <= a[j-2]) || ( a[j] >= a[j-1] && a[j-1] >= a[j-2])) ){//按照题目给出条件判断是否继续循环
            step ++;
            j ++;
        }
        // 更新最长Zigzag子段长度
        maxn = max(maxn, step + 2); // step是额外的元素个数，+2是因为从i-2开始计算
        step = 0;
    }
    cout << maxn;
    return 0;
}

时间复杂度为 O(n^2)。
空间复杂度为 O(n)。