Home PAT 1051 Pop Sequence
Post
Cancel

PAT 1051 Pop Sequence

Link

思路: 由于入栈顺序是 1, 2, …, n, 因此每次出栈的一定是栈顶元素, 且栈顶元素一定比所有的栈中元素大. 要维护栈中元素大个数 (不能超过 m) 以及栈顶元素 (当前 pop 出来的不能比上一个栈顶元素小).

在代码中, 我用 top 记录栈顶元素, 更新方式是从当前输入的元素 a 开始向下寻找第一个没有 pop 出来的元素 (用数组 v 记录是否被 pop), 如果存在, 那么就是找到的这个元素, 没有的话就是 0.

len 记录当前栈的大小. 计算方法是 len+=(a-pre);, 别忘了在判断结束之后减去当前 pop 出来的这个元素: len--;.

pre 记录上一个 pop 出的元素, 用于计算每次 len 的增加量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int m,n,k,a;
bool v[1010];
int main() {
    scanf("%d%d%d",&m,&n,&k);
    while(k--){
        memset(v,false,sizeof(v));
        bool flag=true;
        int top=0,len=0,pre=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&a);
            if(!flag) continue;
            len+=(a-pre);
            if(a<1||a>n||a<top||len>m||v[a]) flag=false;
            len--;
            top=a-1;
            while(top>=1&&v[top]) top--;
            v[a]=true;
            pre=a;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.