PopPush市有一个著名的火车站。那个里的乡村是令人难以置信的丘陵。车站 建于上世纪。不幸的是,当时资金极其有限。有可能 仅建立表面轨迹。此外,事实证明,该站可能只是一个死胡同 (见图片),由于缺乏可用空间,它只能有一个轨道。 当地的传统是,每一列从A方向到达的火车都会继续朝A方向行驶 B与教练以某种方式重组。假设从A方向到达的列车 N≤1000节车厢,按递增顺序1、2、…、,N.列车重组主管必须 知道是否有可能在B方向继续指挥教练,以便他们的命令 是a1.a2,…,aN。帮助他并编写一个程序,决定是否有可能获得所需的 教练的顺序。你可以假设,在他们离开火车之前,单节车厢可以与火车断开 进入车站,他们可以自行移动,直到他们在B方向的轨道上 也可以假设在任何时候都可以根据需要在车站内设置任意数量的客车。 但一旦一辆客车进站,它就不能沿a方向返回轨道,也不能返回一次 它已沿方向B离开车站,它不能返回车站。
输入 输入文件由行块组成。除最后一个区段外,每个区段描述一列列车 对其重组提出更多要求。在块的第一行中,描述了整数N 在上面在块的下一行中的每一行中,N.最后一行 块仅包含“0”。 最后一个块仅包含一行包含“0”。 输出 输出文件包含与输入文件中具有排列的行相对应的行。A行 如果可以按照 输入文件的相应行。否则包含“否”。此外,后面还有一个空行 这些行对应于输入文件的一个块。输出文件中没有对应的行 到输入文件的最后一个“空”块。
Sample Input 5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0 Sample Output Yes No
Yes
思路
如果n不为0,且读入的车厢编号不为0,则读入车厢顺序,放入队列b。初始化队列a,将1~n入队。
如果队列a空,且队列b的队头不等于栈s栈顶,说明该情况不可能存在,跳出循环; 如果栈s非空且队列b的队头等于栈s的栈顶,让队列b队头出队且栈s栈顶出栈,车厢驶出车站到达B; 如果队列a非空,且队列a的队头和队列b的队头相等,让队列a和队列b的队头出队,车厢从A到达B; 如果队列a非空,将队列a的队头放入s后出队,车厢从A进入车站。 用while重复,直到将队列a和栈s清空。
队列a和栈s清空后,如果队列b非空,说明该情况不可能存在,输出No,否则输出Yes。
AC代码
/*
stack
AC
*/
#include <iostream>
#include <stack>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;
int main()
{
int n;
while (cin >> n)
{
if (!n)
{
break;
}
int t;
while (cin >> t)
{
stack<int> s;
queue<int> a;
queue<int> b;
if (t)
{
b.push(t);
for (int i = 1; i <= n; i++)
{
a.push(i);
}
for (int i = 0; i < n - 1; i++)
{
cin >> t;
b.push(t);
// cout << t << endl;
}
}
else
{
break;
}
while (!(a.empty() && s.empty()))
{
if (a.empty() && (b.front() != s.top()))
{
// A空且B与S不能消去
break;
}
else if (!s.empty() && (b.front() == s.top()))
{
// B与S消去
b.pop();
s.pop();
}
else if (!a.empty() && (b.front() == a.front()))
{
// A与B消去
b.pop();
a.pop();
}
else if (!a.empty())
{
// A放进S
s.push(a.front());
a.pop();
}
// cout << b.empty() << endl;
}
if (b.empty())
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
cout << endl;
}
return 0;
}
标签:文件,队列,题解,队头,int,车厢,车站,UVA,514
From: https://blog.51cto.com/HEX9CF/7724916