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,3，…，N其实是（废话本来就是）一个队列(下面记作seq)，然后在弄一个容易被填满的栈…
以下栈底、队首用#号标识
然后看测试的序列，比如5 6 4 3 7 2 1，
1.先看栈顶元素，如果栈顶元素就是输入的元素的话，那就弹栈，然后继续循环
2.如果不是，那么就要将队列的头一直取出，填到栈里面，
直到：(A)栈满了，那么失败了
(B)现在栈顶的元素就是我们的输入元素，那么继续读下一个测试的数字
测试序列5 6 4 3 7 2 1中，一开始的元素是5，于是不断的从1234567这个队列中取头部出来，压栈，然后
栈S : #1 2 3 4 5
seq: # 6 7
满足调节后，下一个循环查看的时候，发现栈顶的5刚好是我们的输入元素，于是序列指针移到6上面，并且弹出5，
经过差不多的过程，变成这样
栈S : #1 2 3 4 6
seq : #7
之后这样
栈S : #1 2 3 4
seq : #7
,
栈S : #1 2 3
seq : #7
,
栈S : #1 2
seq : #7
,
栈S : #1 2 7
seq : #
,
栈S : #1 2
seq : #
,
。。。直到尽头，然后成功了
=======================================================
具体实现可能跟刚才的说法略有不一致，但是原理是一样的。
#include
#include
#include
using namespace std;
int main()
{
int M, N, K;
queue sequences;
queue copy_of_seq; //为了防止重复生成浪费时间
scanf("%d %d %d", &M, &N, &K);
//生成seq队列
for(int i=1; i s;
bool failed = false;
int input_val;
for(int i=0; i= M) //要留一个给后面再读入的相等的元素
{
failed = true;
break;
}
}
if( failed )
{
printf("NOn");
}
else if( copy_of_seq.empty() )
{
failed = true;
printf("NOn");
}
else
{
//成功了..
//s.push( copy_of_seq.front() ); (反正还要pop，不搞了)
copy_of_seq.pop();
}
//如果头部还是与数字不同，那就fail
}
if (!failed)
printf("YESn");
}
return 0;
}
测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 0 740 15/15
1 答案正确 0 750 3/3
2 答案正确 0 790 2/2
3 答案正确 0 790 2/2
4 答案正确 0 750 1/1
5 答案正确 0 780 2/2
