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:
|
1 2 3 4 5 6 |
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:
|
1 2 3 4 5 |
YES NO NO YES NO |
C++测试代码:
|
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 45 46 47 48 49 50 |
//梁笔记 //https://zouzhongliang.com/ #include <iostream> using namespace std; bool IsPop(int* SeqNumbers, int* Numbers,int len, int Stacksize) { int top=0; //表示栈顶 int Num=0; //表示栈内元素 for(int j=0;j<len;j++){ while(Numbers[top] != SeqNumbers[j] ){ Numbers[++top]=++Num; if(top > Stacksize) return 0; } top--; //pop弹出 } return 1; } int main() { int M,N,K; cin>>M>>N>>K; int* Numbers = new int[N]; for(int i=1;i<=N; i++){ Numbers[i-1] = i; } for(int j=0;j<K;j++){ int* SeqNumbers = new int[N]; for(int i=0;i<N; i++){ cin>>SeqNumbers[i]; } if (IsPop(SeqNumbers,Numbers,N,M)) cout<<"YES"<<endl; else cout<<"NO"<<endl; delete[] SeqNumbers; } delete[] Numbers; } |
测试结果：
