[UVA]UVA – 514 Rails – 铁轨

题目地址:

https://cn.vjudge.net/problem/UVA-514

题目描述:

(有道翻译)

Background
背景

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.
在PopPush市有一个著名的火车站。那里的乡村多得令人难以置信。这个车站建于上个世纪。不幸的是,当时的资金非常有限。只可能建立一个表面轨迹。此外,事实证明,空间站可能只是一个没有出路的地方(见图),由于缺乏可用的空间,它只能有一条轨道。

QQ截图20170710172701

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N ≤ 1000 coaches numbered in increasing order 1, 2, . . . , N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1.a2, . . . , aN . Help him and write a program that decides whether it is possible to get the required order of coaches.
当地的传统是,每一辆从A方向来的列车都在B方向上继续前进,而教练在某种程度上进行了重组。假设从A方向到达的列车有N千名教练,数量增加了1、2、……N.培训机构的负责人必须知道,是否有可能将指导教练继续朝B方向发展,以便他们的订单将是a1。a2。,aN。帮助他,写一个程序来决定是否有可能得到教练的要求。

You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.
你可以假设单教练可以断开火车之前进入车站,他们可以移动,直到他们在跑道上的方向b .你也可以假设在任何时候可以有必要尽可能多的教练在车站。但是一旦一个教练进入了车站,它就不能回到a的轨道上,而且一旦它离开了车站,它就不能再回到车站了。

The Input
输入

The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, . . . , N. The last line of the block contains just ‘0’.
The last block consists of just one line containing ‘0’.
输入文件由几行代码组成。除了最后一个阶段,每个模块都描述了一列火车,可能还需要更多的重组需求。在该块的第一行中,有上述的整数N。每条线的下一条线都有一个1 2。。。这个块的最后一行只包含“0”。
最后一个块包含一个包含“0”的行。

The Output
输出

The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains ‘Yes’ if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains ‘No’. In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last “null” block of the input file.
输出文件包含与在输入文件中排列的行对应的行。输出文件的一行包含“Yes”,如果可以按照输入文件相应行所要求的顺序排列这些教练。否则它包含“不”。此外,在与输入文件的一个块对应的行之后,还有一个空行。输出文件中没有对应于输入文件的最后一个“null”块的行。

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


我的分析

在做本题之前,我有在上学期的数据结构课中听老师说过,这种出栈顺序,如果存在 左 > 右 > 中 的情况,则不能满足出栈顺序。比如说,若存在 5 3 4 2 1 的出栈顺序,其中5 3 4这个部分存在 左 > 右 > 中 的情况。由于5先出栈,则3不可能比4更早出栈。

但是本题若采用这种思路去做,则需要嵌套多个循环,因为我们不得不判定某个存在 右 > 中 的情况,在 中 这个数字左边是否有比 右 更大的数字。这样的话又需要一个循环。

不过,既然本题很明显图都画成了栈的形式,那么我们就直接给一个栈。然后再根据出栈顺序逆着放回栈中,读取栈顶,如果栈顶为入栈顺序的倒序的元素(最后一个入栈的值)。那么将该值出栈。同时出栈后的栈顶如果也满足条件,那么继续出栈。直到不满足条件。不满足条件,则加入一个新的出栈元素,再继续进行判定。如果出栈顺序合理,则最后栈必为空。如不合理,则栈必不为空。

(我实在不知道怎么说比较好。。轻喷)

代码