Uva514 Rails(铁轨)
题目描述:
某城市有一个火车站,有n节车厢从A方向驶入车站,按进站的顺序编号为1-n.你的任务是判断是否能让它们按照某种特定的
顺序进入B方向的铁轨并驶入车站。例如,出栈顺序(5 4 1 2 3)是不可能的,但是(5 4 3 2 1)是可能的。
题目分析:
为了重组车厢,借助中转站,对于每个车厢,一旦从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;
}
}
}
上一篇: 怎么将从数据库取得的数据循环写入5个dl
下一篇: Python自动查询考研成绩并发送到邮箱
推荐阅读
-
首次来ITEYE,学习Ruby On Rails,资料较少,所以自己也总结一下吧 rubyrailsiteye
-
Rails连接PostgreSQL错误:psql: 致命错误: 用户 “postgres” Ident 认证失败
-
[ Ruby on Rails ] RedisLogger – a better redis log
-
[ Ruby on Rails ] Ruby 與 Redis 整合之相關資源整理
-
rails中覆盖to_json方法的注意事项
-
开始探索Linux上的Rails
-
发现rails已经打上了2.3.0 tag了
-
rails中覆盖to_json方法的注意事项
-
分享我的emacs配置-用于Ruby on Rails开发
-
与Rails REST亲密接触 RailsRESTXMLRubyMySQL