点击打开链接
题意：有一铁轨如下图，有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; }
