[PAT A1051]Pop Sequence

题目描述

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.

输入格式

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.

输出格式

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

输入样例

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

解析

题目首先要求输入n,m,k三个数，n表示栈的最大容量，m表示有多少个数，k表示有多少个序列需要我们判断。题目的意思就是说对于容量是n的栈，我们按照1、2、3、4、5、6、7的顺序压栈，然后需要我们判断是否存在需要检验的一个序列，使得元素可以按照给出的序列出栈。例如1，2，3，4，5，6，7这个序列，我们首先1压栈，马上1出栈，2压栈，2出栈……，这样我们压栈顺序是按照1，2，3，4，5，6，7来的，存在1，2，3，4，5，6，7这样的出栈顺序，故输出YES。需要注意的就是栈是有容量的，所以一旦容量超过，立马判断这样的序列是不存在的。

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
	int n, m, k;
	stack<int> st;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < k; i++) {
		int p = 1;          //当前需要压入的元素值
		bool judge = true;  //判断是否该序列符合条件
		while (!st.empty()) st.pop(); //首先清空栈
		for (int j = 0; j < m; j++) {
			int temp;
			scanf("%d", &temp); //当前需要出栈的元素
			while (p <= temp) { //从p到当前需要出栈的元素逐一压栈
				st.push(p);
				if (st.size() > n) { //一旦溢出，就判错
					judge = false;
					break;
				}
				p++;
			}
			if (st.top() != temp) { //如果栈顶元素不为temp，也判错
				judge = false;
				continue;
			}
			else st.pop(); //栈顶元素就是需要出栈的元素，那么pop掉该元素
		}
		if (judge) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}