算法竞赛入门经典第六章(例题) B - Rails(涉及到栈的运用)

2020年1月26日 36点热度 0条评论 来源: haixinjiazu

题目:B - Rails

原题链接:https://cn.vjudge.net/contest...

题目大意:先输入一个表示火车的节数,火车原本是按从1到n的顺序,但是一起进的还是分开进的是不一定的。之后输入自己的出站顺序,如果这个顺序可以实现,则输出yes,不能实现则输出no;

思路:利用栈的操作,即先将自己输入的第一个往后依次,先判断栈顶是否为空,如果为空,则从没用进入栈的火车头开始找,如果小于这个要找的元素,则进展,如果大于,则结束寻找,找完之后再判断其栈顶和自己找的是否一样(注意进栈的火车节不允许退出去),如果不为空则判断其栈顶是否一样,如果栈顶一样,则再从火车头中找比这个元素小的或者等于的入栈,最后比这个要找的元素小的或者等于全入栈之后,在判断其栈顶是否和要找的这个元素相同;(中间有些地方能直接判断不成立的,则可以直接退出)

代码:

#include<stdio.h>
#include<string.h>

int my_size=0;
int mystack[1010];
int main()
{
    int N;
    int a[1005],tag=0,temp=1,index;
    while(scanf("%d",&N)!=EOF&&N!=0)
    {
    while(1)
    {
        my_size=0;tag=0;temp=1;
        scanf("%d",&a[0]);
        if(a[0]==0)
            break;
        index=1;
        for(int i=1;i<N;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<N;i++)
        {
            if(my_size==0)
            {
                if(index==a[i])
                {
                    index++;
                    continue;
                }
                while(index<a[i])
                {
                    mystack[tag++]=index++;my_size++;
                    }
                if(index>a[i])
                    temp=0;
                index++;
            }
            else
            {
                while(index<=N&&mystack[my_size-1]!=a[i])
                {
                    mystack[tag++]=index++;
                    my_size++;
                }
                if(mystack[my_size-1]!=a[i])
                {
                    temp=0;}
                else
                {my_size--;tag--;}
            }
            if(temp==0)
                break;
        }
        if(temp)
            printf("Yes\n");
        else
            printf("No\n");
    }
    printf("\n");
    }
    return 0;
}
    原文作者:haixinjiazu
    原文地址: https://segmentfault.com/a/1190000012725585
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。