Xxy 的車廂調度
(train.cpp/c/pas)
Description
有 一 個 火 車 站 ， 鐵 路 如 圖 所 示 ，每輛火車從 A 駛入，
再從 B 方向駛出，同時它的車廂可以重新組合。假設
從 A 方向駛來的火車有 n 節（n<=1000） ，分別按照順
序編號為 1，2，3，…，n。假定在進入車站前，每節
車廂之間都不是連著的，并且它們可以自行移動到 B
處的鐵軌上。 另外假定車站 C 可以停放任意多節車廂。
但是一旦進入車站 C，它就不能再回到 A 方向的鐵軌
上了，并且一旦當它進入 B 方向的鐵軌，它就不能再
回到車站 C。
負責車廂調度的 xxy 需要知道能否使它以
a1,a2,…,an 的順序從 B 方向駛出，請來判斷能否得到
指定的車廂順序。
Input
輸入文件的第一行為一個整數 n，其中 n<=1000，表示有 n 節車廂，第二行為 n 個數字，表
示指定的車廂順序。
Output
如果可以得到指定的車廂順序，則輸出一個字符串”YES”，否則輸出”NO”（注意要大寫，不
包含引號） 。還有，xxy 說了 這題 AC 有糖吃。
Example
train.in train.out
5
5 4 3 2 1
YES
Hint
對于 50%的數據，1<=N<=20。
對于 100%的數據，1<=N<=1000。

思lu:這個棧不會上溢，所以不能成立的原因只有當要出車1的時候上邊有車2等阻攔；

Top作為棧頂所以當B數組為當前需要top到達的車的位置，stack[top-1]==0&&top!=b[i])||top-1==b[i]時top—若top最后==車則本次可以成立不等則判斷否return

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 using namespace std; 7 int b[1003]; 8 int top=1,n; 9 bool flag=false; 10 int stack[1003]; 11 void mdzz() 12 { 13 for(int i=1;i<=n;i++) 14 { 15 if(top<b[i]) 16 { 17 while(top != b[i]) 18 { 19 top++; 20 } 21 stack[b[i]]=0; 22 } 23 else if(top>b[i]) 24 { 25 while((stack[top-1]==0&&top!=b[i])||top-1==b[i]) 26 { 27 top--; 28 } 29 if(top!=b[i]) 30 { 31 flag=true; 32 return; 33 } 34 else stack[b[i]]=0; 35 } 36 37 } 38 } 39 int main() 40 { 41 freopen("train.in","r",stdin); 42 freopen("train.out","w",stdout); 43 scanf("%d",&n); 44 for(int i=1;i<=n;i++) 45 { 46 stack[i]=1; 47 scanf("%d",&b[i]); 48 } 49 mdzz(); 50 if(flag==1)printf("NO"); 51 else printf("YES"); 52 fclose(stdin); 53 fclose(stdout); 54 return 0; 55 }

?

轉載于:https://www.cnblogs.com/sssy/p/6679640.html

總結

以上是生活随笔為你收集整理的GRYZ 模 拟 赛 系 列 Xxy 的车厢调度的全部內容，希望文章能夠幫你解決所遇到的問題。

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