题解 P1420 【最长连号】

SHM1847575517 · 2019-11-01 23:57:03 · 题解

本蒟蒻的第一篇题解。。。。

首先捏本蒟蒻是用栈做的，代码应该比较好理解吧

稍微解释一下思路，我们用栈维护题目中所说的一个连续自然数序列，如果遇到连续自然数，即将要入栈的数等于栈顶数加一，那么就把它PUSH♂进去 ，如果遇到不是连续的自然数~~就是要入栈的那个数不等于栈顶的数+1，就把整个栈清♂空，并且记录下之前自然数序列的长度，如果大于历史记录，就更新ans。之后再向栈里继续PUSH♂新元素~~，遍历一遍O(n)完成。

#include<iostream>
#include<cstdio>

using namespace std；
const int MAXN = 10005;
int a[MAXN];

int main()
{
    int n,x,top=0,ans=0;//定义了一个指向栈顶元素的指针，默认指向0
    cin>>n;
    a[top] = 0x7fffffff;//这里有玄机
    for(int i=2;i<=n;i++)
    {
        cin>>x;
        if(x!=a[top]+1) //如果不是连续自然数，就清空栈，并将新数字 
        {               //入栈，同时更新最大长度记录
            if(top>ans) ans = top;
            top=0;         
            a[++top] = x;  
        }           
        else a[++top] = x;//是连续自然数，继续入栈
    }
    cout<<ans;
    return 0;
}

这里来解释一下a[0]=0x7fffffff的原因，因为if(x!=a[top]+1)。在输入第一个元素时它的位置应该在a[1]而此时top指向a[0]，于是乎a[0]+1肛♂好爆掉♂int于是a[0]+1变成了RBQ-1，条件成立，我们就可以安心向栈里放入第一个元素啦。