题解：P15705 [2018 KAIST RUN Spring] Zigzag

· · 题解

题解：P15705 [2018 KAIST RUN Spring] Zigzag

题目描述：

如果一个序列中不存在连续三个元素是单调的，则称该序列为“Zigzag”序列。

更正式地说，长度为 N 的序列 A 是 Zigzag 序列，当且仅当对于所有 i（1 \le i \le N − 2），既不满足 A_i \le A_{i+1} \le A_{i+2}，也不满足 A_i \ge A_{i+1} \ge A_{i+2}。

给定一个长度为 N 的序列 A，你需要找出 A 的一个最长子段，该子段本身是一个 Zigzag 序列。长度为 M 的序列 B 是长度为 N 的序列 A 的子段，当且仅当存在某个 i，使得 B_1 = A_i,B_2 = A_{i+1} ⋯,B_M = A_{i+M-1} 成立。

思路：

使用滑动窗口维护当前合法的 Zigzag 子段：

用 l 标记当前窗口的左边界。

遍历数组时，检查当前三元组是否违反 Zigzag 规则，如果违反，则将左边界移动到当前三元组的中间位置（因为前两个元素仍然可能和下一个元素形成合法序列）。

遍历过程中持续更新窗口的最大长度。

具体思路见代码注释。

代码：

#include<bits/stdc++.h>//万能头文件。
using namespace std;
bool fun(long long a,long long b,long long c)//判断三个连续元素是否违反Zigzag规则。
{
    return a<=b&&b<=c||a>=b&&b>=c;//检查是否单调递增或单调递减。
}
long long n,a[5005],maxx=2,l;//开long long，maxx为最长Zigzag子段长度，至少为2，l为滑动窗口左边界。
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);//快速读入。
    cin>>n;//输入长度。
    for(int i=0;i<n;i++)
        cin>>a[i];//输入。
    if(n<=2)//长度小于等于2时直接返回。
    {
        cout<<n<<endl;
        return 0;
    }
    for(int r=2;r<n;r++)
    {
        if(fun(a[r-2],a[r-1],a[r]))//检查当前窗口的最后三个元素是否合法。
            l=r-1;//违反规则，将左边界移动到r-1（保留最后两个元素）。
        maxx=max(maxx,r-l+1);//更新最大长度。
    }
    cout<<maxx<<endl;//输出。
    return 0;//好习惯。
}