706
技術社區[雲棲]
算法訓練-鐵軌
題目描述：
某城市有一個火車站，鐵軌鋪設如圖所示。
有n節車廂從A方向駛入車站，按進站順序編號1～n。
現讓這些火車按照某種特定的順序進入B方向的鐵軌並駛出車站。
為了重組車廂，可以借助中轉站C。
C是一個可以停放任意多節車廂的車站，但由於末端封頂，駛入C的車廂必須按照相反的順序駛出C。
對於每個車廂，一旦從A移入C，就不能再回到A了；一旦從C移入B，就不能回到C了。
換句話說，在任意時刻，隻有兩種選擇：A→C和C→B。
請編程判斷判斷：按給定的出站順序，火車能否出站。
樣例輸入：
5
1 2 3 4 5
5
5 4 1 2 3
6
6 5 4 3 2 1
樣例輸出：
Yes
No
Yes
本題為了訓練棧的應用
AC代碼：
#include<stdio.h>
int a[2000],b[2000],stack[2000];
int main()
{
int i,j,n,top,k;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);//輸入測試隊列
for(i=0;i<n;i++)
b[i]=i+1;//隊列初始化
top=0;k=0;j=0;i=0;
stack[top++]=b[0];//棧頂元素初始化
while(k!=n)//如果出戰元素剛好為輸入的車廂個數，就退出
{
if(i==n)//隻要車廂遍曆完，就退出
break;
if(stack[top-1]!=a[j])//如果棧頂元素不等於測試元素
{
i++;//繼續入棧
stack[top++]=b[i];
}
else
{
k++;//如果等於出站元素，棧頂元素出棧，並且標記加1
top--;
j++;//測試數組向後移動
}
}
if(k==n)//如果成功出戰元素剛好為輸入的測試車廂個數，說明出站成功
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
最後更新：2017-04-03 12:55:39