c123 - 00514 - Rails
題目描述
題目描述了一個火車調度問題。火車有 N 節車廂，編號 1 到 N。火車從 A 方向進入車站，需要以特定的順序從 B 方向離開。給定一個車廂排列順序，判斷是否能按照該順序離開車站。
解題思路
這題可以使用堆疊來模擬火車進出車站的過程。我們將目標排列的車廂一個個嘗試放入堆疊中。如果當前要放入的車廂編號與堆疊頂部的車廂編號相同，則將堆疊頂部的車廂彈出，表示該車廂已成功離開車站。如果當前要放入的車廂編號與堆疊頂部的車廂編號不同，則將該車廂放入堆疊中。如果所有車廂都已嘗試放入堆疊，且堆疊為空，則表示該排列是可行的，輸出 "Yes"。否則，輸出 "No"。
複雜度分析
- 時間複雜度: O(N^2) (最壞情況下，每個車廂都需要遍歷堆疊)
- 空間複雜度: O(N) (堆疊最多存儲 N 個車廂)
程式碼
#include <iostream>
using namespace std;
int a[1001],sc[1001],it,it2;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
while(cin >> n){
if(n==0)break;
while(cin >> a[0]){
if(a[0]==0){
cout << "\n";
break;
}
for(int i=0;i<n;++i){
a[i+1]=0;
sc[i]=0;
}
it=0;it2=0;
for(int i=1;i<n;++i)
cin >> a[i];
for(int i=0;i<n;++i){
sc[it]=i+1;
++it;
while(sc[it-1]==a[it2]&&it){
sc[it]=0;
a[it2]=0;
--it;
++it2;
}
}
if(it2==n)
cout << "Yes\n";
else
cout << "No\n";
}
}
}