题目
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
思路
本题正常解法是
- 读取栈容量M，数列长度N，数列条数K
- 根据容量M创建一个栈，读入第一个数字
- 从1开始压栈，压栈的同时判断是否溢出，直到与读入数字相同，弹栈
- 读入下一个数字，与栈顶元素比较，等于则弹栈
- 小于说明违规弹栈flag置为1，大于说明还要压栈同时判断是否溢出
- 直到数列比较完，根据flag值输出yes或no，然后读入下一个队列
在下的解法（不如正常解法，别学）
- 数组结构{flag（是否出栈），num（前面还有多少元素未弹栈）}
- 读取栈容量M，数列长度N，数列条数K
- 创建数组S[N]，flag初始化为0，num初始为0、1、2…N-1，下标即数列
- 读入数字i，判断S[i].num与K的大小，小于说明未溢出
- 判断i与前一个出栈的元素大小，大于则无事发生
- 小于则判断两者之间是否还有未出栈元素，即S[t].num-S[i].num
- 循环N次读完一个队列，初始化数组，开始下一个队列
本题的坑
没有，思路很简单
吐槽
在下还沉浸在上一道题没回过神来，导致下意识使用了数组，但本题用栈直接走一遍更简单。这道题只能说在下想麻烦了，纯纯的累傻小子呢
又犯了低级错误，写程序时忘记在切换队列时初始化数组和其他变量了
