1051 Pop Sequence

题目描述
解题思路：根据栈的特性可以总结如下过程：记录当前读入的最大数为$c_{max}$，当前读入的数为$c$，则有以下两种情况：(1)$c_{max}>c$,则将$c到c_{max}$的数字全部压入栈中。在压的过程如果栈满，则说明这个序列不合法。（2）)$c_{max}<c$，则判断栈顶的数字是否为当前这个c，如果不是说明序列不合法。

#include
#include
using namespace std;
int main(){
    int n,m,c;
    cin>>c>>m>>n;
    while(n--){
        stack<int> s;
        int cur_max = -1;
        bool flag = true;  
        int sq[1010];
        for(int i = 1;i <= m;i++)
            cin>>sq[i];
        for(int i = 1;i <= m;i++){
            if(cur_max == -1 || sq[i] > cur_max)
            {
                int j;
                if(cur_max == -1)
                    j = 1;
                else j = cur_max + 1;
                for(;j <= sq[i];j++){
                    if(s.size() >= c)
                    {
                        flag = false;
                        break;
                    }
                    else s.push(j);
                }
                cur_max = sq[i];
                s.pop();
            }else{
                if(s.size() == 0 || s.top() != sq[i]){
                    flag = false;
                    break;
                }
                s.pop();
            }
        }
        if(flag)
           cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
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
33
34
35
36
37
38
39
40
41
42
43
44