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. 栈不够长。

读入序列后，我们从左往右遍历序列：

• 如果走到某个元素发现符合失败原因，就break；
• 如果能遍历完序列，说明能成功；

代码

#include <iostream>
#include <stack>
using namespace std;
int main() {
    int MAXLEN, NUM, K;
    cin >> MAXLEN >> NUM >> K;
    while(K--) {
        stack<int> myStack;
        int array[10001] = {0x0};
        // Read sequence
        for(int i = 0; i < NUM; i++) 
            cin >> array[i];
        // Walk sequence
        int pos(0);
        int push_counter(0);
        for(pos = 0; pos < NUM; pos++) {
            // array[i] not in stack, do push operation
            if( array[pos] > push_counter ) {
                while( myStack.size() < MAXLEN && array[pos] > push_counter ) {
                    myStack.push(push_counter+1);
                    push_counter++;
                }
            }
            // Stack too short
            if( array[pos] > push_counter )    break;
            // array[pos] not equal top of stack
            if( array[pos] != myStack.top() )    break;
            myStack.pop();
        }
        if(pos == NUM)   cout << "YES\n";
        else   cout << "NO\n";
    }
    return 0;
}