XDOJ-267 判断栈输出顺序正确与否

本题算是比较难的，如果要遍历每一个输出进行比较的话将会十分困难，但是通过逆向，我们将可以化难为易。基本思路是：将输入的出栈序列按照顺序进行弹出，如果能够弹出就证明输出正确，否则就输出错误。如按照此顺序弹出：3 2 1 7 5 6 4，那么就是先入栈123，之后进行比较将3出栈，再比较，将2、1分别出栈，再入栈4 5 6 7，再进行比较，出栈7，最后发现无法在不出栈6的情况下出栈5，则证明此顺序错误。但是，在这之中亦需要考虑栈是否已满，能否入栈等问题，因为此问题中栈的容量也是不确定的因素。

问题描述

给定一个栈，其中最多存储M个数据。将N个数据以1,2,3,...,N的顺序压栈，然后再随机弹栈。判断一下哪些是有可能的弹栈顺序，而哪些不是。例如M是5，N是7，我们可以得到1, 2, 3, 4, 5, 6, 7的弹栈顺序，而不能得到3, 2, 1, 7, 5, 6, 4这样的弹栈顺序。（M，N<=1000）

输入说明

输入包含了一种情况下的测试数据。在每种情况下，有三组输入数据：

第一组列在首行，包含了三个数据：栈的最大容量M，压栈数据长度N，要验证的弹栈序列个数K。

第二组为压栈数据：N个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。

第三组为K行数据，每行包括了一个需要验证的弹栈序列（含N个数据）。

同行数据间以空格隔开。

输出说明

输出应该包括K行，包行了对每个输入的验证序列，输出的一个判断结果。如果这个弹出序列可能发生，就输出“YES”，否则就输出“NO”。

输入样例

5 7 5

1 2 3 4 5 6 7

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

#include
#include
#include
#include
using namespace std;
int main()
{
	int m,n,times, tempKey,keyi,tempNum;
	keyi = 0;
	
	int key[1005] = {};
	cin >>m>> n>>times;
	stack<int> s;
	queue<int> q;
	for (int i = 0; i < n; i++)
	{
		cin >> key[i];
	}
	for (int ii = 0; ii < times; ii++)
	{
		int Numi = 0;
		int Num[1005] = {};
		for (int i = 0; i < n; i++) //Num[]为待测试的数组
			cin >> Num[i];
		tempKey = key[keyi];
		s.push(tempKey);
		keyi++;
		for (;keyi < n; ) 
		{
			while (s.empty() || s.top() != Num[Numi])
			{
				s.push(key[keyi]);
				keyi++;
			}
			if (s.size() > m)
				break;
			while (!s.empty() && s.top() == Num[Numi])
			{
				s.pop();
				Numi++;
			}
		}
		if (s.empty())
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		while (!s.empty())
		{
			s.pop();
		}
		keyi = 0;
	}
	
	return 0;
}

欢迎大家关注：https://github.com/XDUgaile

写完的一些东西会不定时丢上去。