欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Uva514 Rails(铁轨)

程序员文章站 2022-04-09 13:10:10
...

题目描述:

某城市有一个火车站,有n节车厢从A方向驶入车站,按进站的顺序编号为1-n.你的任务是判断是否能让它们按照某种特定的
顺序进入B方向的铁轨并驶入车站。例如,出栈顺序(5 4 1 2 3)是不可能的,但是(5 4 3 2 1)是可能的。
Uva514 Rails(铁轨)

题目分析:

为了重组车厢,借助中转站,对于每个车厢,一旦从A移入C就不能回到A了,一旦从C移入B,就不能回到C了,意思就是A->C和C->B。
而且在中转站C中,车厢符合后进先出的原则。故这里可以看做为一个栈。

具体思路是从B方向的序列 倒推 栈C 的入栈出栈顺序,
以B方向的5,4,3,2,1为例子:从一个数字5开始,要想从栈C拿到5号车厢,5号车厢得入栈C,且5号车厢处于栈顶位置,为了保证5号车
厢在栈C中,必须把1,2,3,4,5(小于等于5的车厢)压入栈C中,入栈操作完毕后,然后取出栈顶元素,此时取出来的是5,和B
方向的第一个数字5一致,我们接着看B方向的第二个数字4,因为4号车厢已压入栈C中,所以不需要入栈操作,直接取出栈顶元素,
进行对比,此时取出来的栈顶元素正是4,符合要求,接下来看B方向的第三个数字3,后面就依次类推了
下面我们以5 4 1 2 3为例子:
还是从B方向的第一个数字开始,这个数字是5,所以依次把1 ,2,3,4,5压入栈C中,然后取出栈顶元素5,与B方向的第一个数字
5一致,然后校验B方向的第二个数字4,由于4已经入栈了,取出栈顶元素,取出来一看是4,符合,然后校验B方向第三个数字1,由于
4已经入栈了,取出栈顶元素,取出来一看是3,不等于数字1,所以 5 4 1 2 3 是一个非法序列

以上便是做题思路,具体java代码如下

import java.util.LinkedList;
import java.util.Scanner;
/**
 * @author 许湘扬
 * @email  aaa@qq.com
 * @detail Uva514 Rails(铁轨) 
 */
public class Main 
{
    public static void main(String[] args)
    {
        Scanner cin=new Scanner(System.in);
        int[    ]  result=new int[1005];
        int n=-1;
        while(  (n=cin.nextInt())!=-1 && n!=0)
        {
            //----------------给B、A区赋予初值-------------------

            while( (result[0]=cin.nextInt())!=-1  )
            {
                if (result[0]==0) {
                    result[0]=-1;
                    System.out.println();
                    break;
                }
                for (int i = 1; i < n; i++) 
                    result[i]=cin.nextInt();
                boolean flag=true;
                int index=1;
                //-------------------------------------------
                LinkedList<Integer> stack=new LinkedList<Integer>();
                for (int i = 0; i < n; i++) 
                {
                    int a=result[i];

                    while(index<=a)//依次把比当前数字小的数字压入栈中
                    {
                        stack.push(index);

                        if (index==a)
                        {
                            index++;
                            break;
                        }
                        index++;        
                    }

                    //取出栈顶元素与当前结果数字对比,不同则是错误的序列
                    if (a!=stack.pop())
                    {
                        System.out.println("No");
                        flag=false;
                        break;
                    }
                }
                if (flag) 
                    System.out.println("Yes");
                result[0]=-1;
            }
            n=-1;
        }
    }
}
相关标签: uva514 java