755
【Tsinghua】列車調度(Train)
這題沒什麼好說的，就是一個棧的實現，因為當時那個OJ不能用STL，就自己寫了一個功能有，但是不完善的棧，反正解出題目了。。。。。。
注意：此題是第二次mooc課程，但是我參加的第一次mooc課，所以ac代碼可能不能直接提交，需要修改
列車調度(Train)
描述
某列車調度站的鐵道聯接結構如圖所示。
其中，A為入口，B為出口，S為中轉盲端。所有鐵道均為單軌單向式：列車行駛的方向隻能是從A到S，再從S到B；另外，不允許超車。因為車廂可在S中駐留，所以它們從B端駛出的次序，可能與從A端駛入的次序不同。不過S的容量有限，同時駐留的車廂不得超過m節。
設某列車由編號依次為{1, 2, ..., n}的n節車廂組成。調度員希望知道，按照以上交通規則，這些車廂能否以{a1, a2, ..., an}的次序，重新排列後從B端駛出。如果可行，應該以怎樣
的次序操作?
輸入
共兩行。
第一行為兩個整數n，m。
第二行為以空格分隔的n個整數，保證為{1, 2, ..., n}的一個排列，表示待判斷可行性的駛出序列{a1，a2，...，an}。
輸出
若駛出序列可行，則輸出操作序列，其中push表示車廂從A進入S，pop表示車廂從S進入B，每個操作占一行。
若不可行，則輸出No。
輸入樣例1
5 2
1 2 3 5 4
輸出樣例1
push
pop
push
pop
push
pop
push
push
pop
pop
輸入樣例2
5 5
3 1 2 4 5
輸出樣例2
No限製
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000
時間：2 sec
空間：256MB
AC的代碼：
#include <stdio.h>
#define MANX 100005
int Stack[MANX];
int Out[MANX];
int sTop=0; //棧頂指針
void push(int a)
{
Stack[++sTop]=a;
}
void pop()
{
sTop--;
}
int top()
{
return Stack[sTop];
}
int main()
{
// in 的時候一定是{1, 2, ..., n}
int n,m;
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++)
scanf("%d",&Out[i]);
//算法開始
int j=0;
for(i=1;i<=n;i++)
{
//如果小於棧頂元素，直接可判斷在棧中而無法出棧
if(Out[i]<top())
{
printf("No\n");
return 0;
}
//直到 Out[i] 的元素全部加入棧
if(j<Out[i])
while(j!=Out[i])
push(++j);
if(sTop>m)
{
printf("No\n");
return 0;
}
if(Out[i]==top())
pop();
}
printf("Yes\n");
return 0;
}
最後更新：2017-04-03 05:39:41