【題目描述】

有一個火車站，鐵路如圖所示，每輛火車從A駛入，再從B方向駛出，同時它的車廂可以重新組合。假設從A方向駛來的火車有n節（n≤1000），分別按照順序編號為1，2，3，…，n。假定在進入車站前，每節車廂之間都不是連著的，并且它們可以自行移動到B處的鐵軌上。另外假定車站C可以停放任意多節車廂。但是一旦進入車站C，它就不能再回到A方向的鐵軌上了，并且一旦當它進入B方向的鐵軌，它就不能再回到車站C。

負責車廂調度的工作人員需要知道能否使它以a1,a2,…,an的順序從B方向駛出，請來判斷能否得到指定的車廂順序。

【輸入】

第一行為一個整數n，其中n≤1000，表示有n節車廂，第二行為n個數字，表示指定的車廂順序。

【輸出】

如果可以得到指定的車廂順序，則輸出一個字符串”YES”，否則輸出”NO”（注意要大寫，不包含引號）。

【輸入樣例】

5
5 4 3 2 1

【輸出樣例】

YES

【提示】

觀察發現，整個調度過程其實是在模擬入棧出棧的過程，而這個過程中，我們可以分成三種狀態：棧前、棧中、棧后。我們可以發現，當某個數字出棧了，說明比它小的數字要么已經出棧了，要么還在棧里，不能是入棧前狀態，并且在棧中的順序是從大到小的(從棧頂往棧底看)，比如出5，那么1，2，3，4要么已經在5之前出了，要么還在棧中（假如1，3，4在棧中，從棧頂往棧底看依次為4，3，1），不能是入棧前的狀態。如果某個數字要出棧，那么當前在棧中的數字都必須小于它，否則就與棧的性質矛盾，不合法，于是我們可以這樣解決：

從第一個數字開始掃描，a[i]表示當前出棧的數字，如果有比a[i]大的數字還在棧中，那么就產生矛盾，輸出“NO”；否則，標記當前數字a[i]為棧后狀態，那么[1, a[i]-1]這些數字如果還沒出棧，標記為棧中狀態。具體我們可以用0表示為確定狀態，1表示棧中狀態，2表示棧后狀態。

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=1000000007; const int N=10000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std; int a[N]; stack<int> S; int main(){int n;cin>>n;for(int i=1;i<=n;i++)//a[i]為到達B站的車廂cin>>a[i];int cur=1;//cur為需要進棧的車廂for(int i=1;i<=n;i++)//進棧,到達A站；出棧,到達B站{while(cur<=a[i])//比a[i]小的車廂都要在棧中S.push(cur++);if(S.top()==a[i])//將a[i]彈出棧S.pop();else{cout<<"NO"<<endl;return 0;}}cout<<"YES"<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的车厢调度（信息学奥赛一本通-T1357）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。