PAT~线性结构Pop Sequence~python

迈不过友情╰ 2022-10-01 04:58 161阅读 0赞

题目描述：

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

### Output Specification: ###

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

### Sample Input: ###

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

### Sample Output: ###

YES
    NO
    NO
    YES
    NO

意思即为：给定一个一定大小的堆栈，还有一组从大到小的数，例如（1,2,3,4,5,6），问这组数是否可以通过堆栈来输出指定的序列。上面的例子的5 7 5，即为堆栈大小为5，长度为7的序列，共有5组测试。

\----------------------------------------------------------答题区----------------------------------------------------------

*  用python来模拟堆栈的一些操作。首先创建一个值全为1，长度为序列长度的数组arr\_lst。
 *  取待输出的数组的序列的值，例如待输出序列第一个元素为3，那么说明1,2,3都要进栈，就把arr\_lst的前三个元素的值都变为2，然后num计数增加为3。
 *  待上面操作结束后，判断num有没有超出栈的大小。
 *  再判断有没有比这个数大的数在栈中，比如3 2 1 7 5 6 4这个序列，当弹出5时，6此时必在栈中，在7那个时候入的栈，所以栈顶应该是6，弹出5是错误的。
 *  如果这些异常都没有发生，就模拟一次出栈的操作。
 *  最后如果所有的都正常运行输出YES，某个地方不正常即输出NO。

s1=input()
    s1=s1.split(" ")
    arr_size=int(s1[0])
    
    for j in range(int(s1[2])):
        s2=input()
        s2=s2.split(" ")
        arr_lst=[1]*int(s1[1])
        error=0
        num=0
    
    #变为int类型
        for i in range(len(s2)):
            s2[i]=int(s2[i])
    
        for i in s2:
    #模拟进栈操作
            for k in range(i):
                if(arr_lst[k]==1):
                    arr_lst[k]=2
                    num+=1
    #超出栈的大小
                if(num>arr_size):
                    print("NO")
                    error=1
                    break
            
            if(error==1):
                break
    #判断是否有大于该数的数在栈中
            if(2 in arr_lst[i:]):
                print("NO")
                error=1
                break
    #模拟出栈操作
            else:
                arr_lst[i-1]=0
                num-=1
        
        if(error==0):
            print("YES")

运行结果：最大耗时：106 ms，最大内存3568 KB。