UVA-514 Rails

本文主要是介绍UVA-514 Rails，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

题意：有一铁轨如下图，有n节车厢从A方向驶入车站，按进站顺序编号1~n，A中进入C的车厢不能再返回A，C中进入B的车厢也不能再返回C。让你判断能否按某特定顺序进如B方向的铁轨，并驶出车站。

分析：铁轨的中转站C是关键，先驶入C的车厢后出，很明显符合栈先进后出的原则，用栈模拟一下即可。任意时刻，只有两种选择，A->C和C->B，当第i节车厢进入C时，判断是否是给定顺序中的下一节车厢，如果是，则出站，并继续判断C中栈顶车厢，如果不是，则A中下一节车厢进C。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXN=1010;
int n,tar[MAXN];int main()
{//freopen("in.txt","r",stdin);while(cin>>n&&n){stack<int> s;while(cin>>tar[1]&&tar[1]){for(int i=2; i<=n; i++)cin>>tar[i];int ok=1,a=1,b=1;while(b<=n){if(a==tar[b]){ a++;b++; }else if(!s.empty()&&s.top()==tar[b]) { s.pop(); b++; }else if(a<=n) { s.push(a);a++; }else{ ok=0; break; }}if(ok) cout<<"Yes"<<endl;else cout<<"No"<<endl;}cout<<endl;}return 0;
}

这篇关于UVA-514 Rails的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---