程序设计在线评测(Online Judge)

从http://acm.hnust.edu.cn/web登录可查看比赛的OI排名分。

问题 1068. -- 车站调度

1068: 车站调度

时间限制: 2 Sec  内存限制: 128 MB
提交: 3266  解决: 937
[提交][状态][讨论版]

题目描述

有顺序排列的1,2, 3,…,n节车厢在入站口等待调度。车站设置了一个栈作为缓冲,这样的话只可能进行下列两个操作之一:

      1)如果还有车厢在入站口,将最前面的入栈缓冲

      (2)将栈顶的车厢驶出车站    

给定一个1n的排列,问其作为出站序列是否合法。

注意:入站顺序为1,2, 3,…,n,即1先入栈...,n最后入栈。

输入

输入包含若干测试用例。每一个测试用例由多行组成。第一行是两个整数n1<=n <= 100)和mn表示入站序列为1nm表示随后有m行出站序列。

nm均为0时表示输入结束。

输出

对应每一个出站序列,合法则输出一行YES,否则输出一行NO

样例输入

3 6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
0 0

样例输出

YES
YES
YES
YES
NO
YES

提示


参见习题集p21 题3.1。


本题主要测试对栈的理解及灵活运用。解本题推荐采用模拟入栈出栈的方式,以训练对栈的运用熟练程度。当然也有其它方法,如推导出规律(出栈序列中存在“大小中”的组合是不行的)后编程求解。

来源

[提交][状态][讨论版]