| 网站首页 | USACO译题 | 编程语言 | 算法艺术 | 数据结构 | 竞赛试题 | oier天地 | 历史荣誉 | 相关软件 | 学校网站 | 留言本 | 
站内导航： 温中信息学竞赛 >> oier天地 >> 解题报告 >> 文章正文 用户登录 新用户注册
zju1259            【字体：小 大】
zju1259BT解法
作者：飞鹰    文章来源：crystalchern    点击数：    更新时间：2005-12-12

Time limit: 1 Seconds   Memory limit: 32768K   Total Submit: 1422   Accepted Submit: 590  

有一个车站，每天都会有N辆车进站，进站按从1~N的顺序进站。现在车站的站长想让这些火车按照特定的顺序出站，问可以做到吗？

当N为5时，出站顺序若为1 2 3 4 5，可以做到，但是顺序若为5 4 1 2 3，则不行。

 

我们可以把火车进站就是压栈，出站则是弹栈。

输入一个N，下接一些出站序列，当读到一个0时，则这个Input Block结束。当N=0时，程序结束。

Sample Input

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

Sample Output

Yes
No

Yes

这个题目的解法本来应该是很简单！

但是crystalchern想到了一个比较BT的方法！耗了一个下午，终于改成功了！

var
  n,sum,i,t,j,m:longint;
  a:array[1..1000]of integer;
  b,c:array[0..1000]of boolean;
  f,ff:boolean;
begin
 把数据读入到a数组；
  f:=true;
  t:=0;
  fillchar(b,sizeof(b),false);
  fillchar(c,sizeof(c),true);
  b[0]:=true;
  for i:=1 to n do
   begin
   while b[t]=false do t:=t-1;            //因为是boolean型的数组，所以需要一个向下搜索是否是最大的数；
   if t   begin
    sum:=0;
    for j:=t+1 to a[i]-1 do         //准备入栈的数；
     begin
      if c[j] then
       begin
        c[j]:=false;                       //标记这个数是否入栈，或者是否已经与A中的数相符合；
        b[j]:=true;
        inc(sum);
       end;
     end;
    t:=t+a[i]-t-1;
    c[a[i]]:=false;
   end
   else
    begin
      if t=a[i] then                    //判断准备入栈的数是否是栈中最新的那个，如果是就直接调出；
       begin
        b[t]:=false;
        c[t]:=false;
        t:=t-1;
       end
      else f:=false;           //如果指针t 比所需出栈的A[i]小，那么说明违反了栈的规则；
     end;
   if f=false then
   begin
    f:=false;
    break;
   end;
   end;
   if f then writeln('Yes')
   else writeln('No');
end.

程序中的t有多种用途！因为在boolean的数组中，所以t 既充当了指针的作用，同时它也表示这个数字的大小。

这种算法在思路上比较复杂，必须要先想通，因为入栈的数是有序的，所以在栈中的数虽然不是连续的，但却也是有序的，因而当我们用boolean的数组的时候，从大到小所有true的数正是栈中的数由上到下的顺序！

 

                                                                                                在此感谢一下crystalchern同学想到了这么bt的算法！
文章录入：lyzh588    责任编辑：lyzh588 
  • 上一篇文章： 一题多解实例

  • 下一篇文章： 没有了
    		•
    【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】
    最新热点 最新推荐 相关文章
    没有相关文章
    　　网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！）

    温州中学信息学竞赛组 本站资料多从网络收集，若有版权问题，请联系！ 站长：舒老师　（办）0577-86786615