您的位置: 首页  >  文章  >  UVA514 Rails 栈的经典应有

UVA514 Rails 栈的经典应有

分类: 文章 • 2024-12-01 11:05:52

题意翻译

某城市有一个火车站，铁轨铺设如图。有n节车厢从A方向驶入车站，按进站的顺序编号为1～n。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如，出栈顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。 为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每节车厢，一旦从A移入C，就不能返回A了;一旦从C移入B，就不能返回C了。也就是说，在任意时刻，只有两种选择：A到C和C到B。

对于每一组数据，第一行是一个整数 NN 。接下来若干行数据，每行 NN 个数，代表 11 ~ NN 车厢的出栈顺序，最后一组数据只有一个整数 00 。对于每一组数据，在最后输出空行。

最后一组数据的 N=0N=0 ，不输出。

感谢@throusea @0_Mr_Wu 提供的翻译

题目描述

PDF

UVA514 Rails 栈的经典应有

输入输出格式

输入格式：

 

UVA514 Rails 栈的经典应有

 

输出格式：

 

UVA514 Rails 栈的经典应有

 

输入输出样例

输入样例#1： 复制

5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

输出样例#1： 复制

Yes
No
Yes

栈的经典应用

解析见：点这里

注意每一个大样例一个换行


#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;
#define N 1100
typedef long long ll;
int n;
int a[N],b[N];
bool ju()
{
    int i=0,j=0;
    stack<int>s;
    while(i<n||j<n)
    {
        if(!s.empty()&&s.top()==b[j]&&j<n)//出栈
        {
           s.pop();
           j++;
        }
        else   ///出栈
        {
          if(i==n)
          {
            return 0;
          }
          s.push(a[i]);
          i++;
        }
    }
    return 1;

}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        if(n==0) break;

        for(int i=0;i<n;i++)
            a[i]=i+1;
        while(~scanf("%d",&b[0]))
        {
         if(b[0]==0) break;
         int flag=0;
         if(b[0]==a[0])
            flag=1;
         for(int i=1;i<n;i++)
         {
         scanf("%d",&b[i]);

         if(b[i]!=a[i])
            flag=1;
         }

        if(!ju()&&flag==1)
            cout<<"No"<<endl;
        else
        {
            cout<<"Yes"<<endl;

        }

        }
        cout<<endl;
    }
    return 0;
}

紫书代码：

#include<cstdio>
#include <cstring>
#include<stack>  
using namespace std;  
const int MAXN=1010;  
int train[MAXN];  

int main()  
{  
    int n,A,B,ok;  
    while(scanf("%d",&n),n)  //uva常用开头
    {  
        stack<int> s;  
        while(1){  
        scanf("%d",&train[1]);  
        if(train[1]==0)  break;  
        {  
        for(int i=2;i<=n;i++)  
        {  
             scanf("%d",&train[i]);  
        }  
        A=B=ok=1;   
        while(B<=n)  //如果驶向B的车个数等于n，则循环结束。   
        {  
            //如果驶向C的车等于驶向B的车的***，直接该将车驶进B
            //可以得出若满足如果驶向C的车等于驶向B的车的***，A车一定直接驶入B
            if(A==train[B]) { A++,B++;}   
            //否则，则判断栈顶的(即在C最上面)车是否等于驶向B的车
            //若成立，则将车驶入B
            else if(!s.empty()&&s.top()==train[B]) {s.pop(),B++;}  
            //将车驶进C   
            else if(A<=n) s.push(A++);  
            //如果车全部都驶入C，循环还没有结束，意味着所给的train顺序不能实现   
            else  
            {  
                ok=0;  
                break;  
            }  
        }  
        printf("%s\n",ok?"Yes":"No");}}  
        printf("\n");  
    }  
}

 

相关推荐