stack-鐵軌問題 - acm1314 @ IT工程師數位筆記本

文章出處

每輛火車都從A方向駛入車站，再從B方向駛出車站，同時它的車廂可以進行某種形式的重新組合。假設從A方向駛來的火車有n節車廂(n<1000)，分別按順序編號為1，2，...,n。假定在進入車站之前每節車廂之間都是不連著的，并且它們可以自行移動，直到處在B方向的鐵軌上。另外假定車站C里可以停放任意多節的車廂。但是一旦當一節車廂進入車站C，它就不能再回到A方向的鐵軌上了，并且一旦當它進入B方向的鐵軌后，它就不能再回到車站C。負責車廂調度的工作人員需要知道能否使它以a1，a2，...，an的順序從B方向駛出。請寫一個程序，用來判斷能否得到指定的車廂順序。

【輸入格式】

輸入由兩行組成：

第一行有n(n<1000),表示有n節車廂。

第二行n個數表示一組需判定的車廂。

【輸出格式】

對于每個輸入輸出有一行,每行根據判斷,如果能正常駛出輸出"YES",否則輸出"NO"。

【輸入輸出樣例】

5 4 3 2 1

Yes

5 4 1 2 3

6 5 4 3 2 1

Yes

 1 #include<cstdio>
 2 #include<stack>
 3 using namespace std;
 4 
 5 const int maxn = 1000 + 10;
 6 int n, target[maxn];
 7  
 8  int main()
 9  {
10      while(scanf("%d", &n)==1)
11      {
12          stack<int> s;
13          int A = 1, B = 1;
14          for(int i = 1; i <= n; i++)
15          scanf("%d", &target[i]);
16          int ok = 1;
17          while(B <= n)          //B表示出棧的車的數量 
18          {
19              if(A==target[B])    //A表示出棧數量加上入棧車輛和 
20              {
21                  A++; B++;
22              }
23              else if(!s.empty()&&s.top()==target[B])
24              {
25                  s.pop(); B++;
26              }
27              else if(A<=n) s.push(A++);
28              else
29              {
30                  ok = 0; break;
31              }
32          }
33         printf("%s\n", ok ? "Yes" : "No");
34      } 
35      return 0;
36  }