PAT甲级1051.

目录

A1051

题目

样例

输入:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出:

YES
NO
NO
YES
NO

思路和坑点

　　采用反向测试的方法，所给序列如果能通过入栈和出栈操作得到就可以以相同的方式逆向获得1-n的进栈序列。从序列的末尾逆序开始，如果栈空或者栈中的数小于序列中的数，就把序列中的数入栈，否则栈中出栈。由于是逆过程，所以读序列进行入栈相当于得到序列时的出栈操作，出栈相当于得到序列时的入栈操作。
　　接下来讨论何时为不能得到：
　　①如果中间过程中栈溢出（即满的时候还要进栈）
　　②如果出栈的序列不是从n-1的

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int m,n,k,cnt=0;
    cin>>m>>n>>k;
    int a[n];
    for(int i=0;i<k;i++){
        stack<int> s;
        cnt=0;                                      //出栈得到1-n序列的逆序时候的计数器 
        int index=n-1;                              //序列判定的下标遍历指针 
        for(int j=0;j<n;j++){                       //读入一组序列 
            scanf("%d",&a[j]);
        }
        while(index>=0){                            //逆序遍历给定的序列 
            if(s.empty()||s.top()<a[index]){
                if(s.size()==m)        break;       //栈溢出，不可得到 
                s.push(a[index]);
                index--;
            }
            else{
                if(s.top()!=n-cnt) break;           //不是按照1-n的顺序入栈，不可得到 
                s.pop();
                cnt++;
            }    
        }
        if(index<0)     puts("YES");                //如果可以正常的反向进行进出栈模拟，认定可以 
        else            puts("NO");                 //如果中途判定不可逆，并且终止循环，认定不可得 
    } 
    return 0;    
}