f105 - 鐵路
題目描述
題目給定一個火車站的鐵軌設計，火車從 A 鐵軌進入，需要按照特定順序到達 B 鐵軌。輸入火車數量 n 和一個包含 n 個火車編號的排列，判斷是否可以按照該排列將火車從 A 鐵軌移動到 B 鐵軌。如果排列中的火車編號與 A 鐵軌上的火車順序一致，則可以成功移動，輸出 "Yes"，否則輸出 "No"。
解題思路
這題的核心是模擬火車的移動過程。我們使用一個 sc 陣列來記錄 A 鐵軌上可移動的火車編號，a 陣列儲存輸入的火車排列。遍歷輸入的排列 a，如果排列中的火車編號與 sc 陣列中的第一個元素匹配，則將該火車編號從 sc 陣列中移除，並將排列中的下一個火車編號考慮。如果排列中的火車編號與 sc 陣列中的第一個元素不匹配，則檢查是否可以將 sc 陣列中的元素移除，因為可能存在前方的火車已經被處理，導致 sc 陣列中的第一個元素不再是下一個應該移動的火車。如果所有火車都能成功移動，則輸出 "Yes"，否則輸出 "No"。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(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";
}
}
}