首页 > 试题广场 >

火车进站

[编程题]火车进站
  • 热度指数：80458 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}火车站一共有 n 辆火车需要入站，每辆火车有一个编号，编号为 1 到 n。
\hspace{15pt}同时，也有火车需要出站，由于火车站进出共享一个轨道，所以后入站的火车需要先出站。换句话说，对于某一辆火车，只有在它之后入站的火车都出站了，它才能出站。

\hspace{15pt}现在，已经知道了火车的入站顺序，你需要计算，一共有多少种不同的出站顺序。按照字典序从小到大依次输出全部的出站顺序。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 10\right) 代表火车的数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq n\right) 代表火车的入站顺序。


输出描述:
\hspace{15pt}输出若干行，每行输出 n 个整数，代表一种出站顺序。你需要按照字典序从小到大依次输出。
示例1

输入

3
1 2 3

输出

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

说明

\hspace{15pt}在这个样例中，每一种出栈顺序的详细出入站状况为（黑色普通字体代表入站、橙色加粗字体代表出站）：
\hspace{23pt}\bullet\,1 \to {\color{orange}{\bf 1}} \to 2 \to {\color{orange}{\bf 2}} \to 3 \to {\color{orange}{\bf 3}}；
\hspace{23pt}\bullet\,1 \to {\color{orange}{\bf 1}} \to 2 \to 3 \to {\color{orange}{\bf 3}} \to {\color{orange}{\bf 2}}；
\hspace{23pt}\bullet\,1 \to 2 \to {\color{orange}{\bf 2}} \to {\color{orange}{\bf 1}} \to 3 \to {\color{orange}{\bf 3}}；
\hspace{23pt}\bullet\,1 \to 2 \to {\color{orange}{\bf 2}} \to 3 \to {\color{orange}{\bf 3}} \to {\color{orange}{\bf 1}}；
\hspace{23pt}\bullet\,1 \to 2 \to 3 \to {\color{orange}{\bf 3}} \to {\color{orange}{\bf 2}} \to {\color{orange}{\bf 1}}。
算法知识视频讲解
添加回答
Python
大溪地渔民头像 大溪地渔民 
def helper(trains, stack, output):
    global total
    if not trains and not stack:
        total.append(output)
        return
    if stack:
        t = stack.pop()
        helper(trains, stack, output+t)
        stack.append(t)
    if trains:
        stack.append(trains.pop())
        helper(trains, stack, output)
        trains.append(stack.pop())


while True:
    try:
        n = int(input())
        trains = input().split()[::-1]
        stack, total = [], []
        helper(trains, stack, "")
        for s in sorted(total):
            print(" ".join(s))
    except:
        break

发表于 2020-12-18 15:53:58 回复(0)
Python
混分兽头像 混分兽
递归可能比较好理解一点： 
all_res=[]
def solver(prefix,my_stack,remain):
    global all_res
    if remain==[]:
        if not my_stack:
            all_res.append(prefix[:])
            return 
        else:
            while my_stack:
                prefix.append(my_stack.pop())
            all_res.append(prefix[:])
            return
    if not my_stack:
        solver(prefix[:],[remain[0]], remain[1:])
    else:
        solver(prefix[:], my_stack[:]+[remain[0]], remain[1:])
        while my_stack:
            prefix.append(my_stack.pop())
            solver(prefix[:], my_stack[:]+[remain[0]], remain[1:])
while True:
    try:
        all_res=[]
        number=int(input())
        remain=input().split()
        solver([], [], remain)
        all_res.sort()
        for string in all_res:
            print(' '.join(string))
    except:
        break


发表于 2020-09-18 14:28:29 回复(0)
Python
牛客904525060号头像 牛客904525060号
看答案都是用递归处理，分享个另类思路。性能略差，比较直白
1：先求出所有车的排列，作为出站序列
2：循环判断该出站序列是否符合要求
    判断逻辑：
        1：任意车n出站后，其前车0~n-1必然在车站内(如果已出站则移除)，n+1~-1则在车站外 
        2：下一车 x  出站，判断x是在站内还是站外。如果是站内则必然是栈顶元素，判断是否相等，如果不相等就撞车了，移除
        3：剩下的就是所有出站序列的集合，排序输出
import itertools

while True:
    try:
        n = input()
        l = input().split(" ")
        all = itertools.permutations(l)

        allc = []
        for out in all:
            b = l.copy()
            station = []
            bool = False
            for car in out:
                if car in station and car != station.pop():
                    # allc.remove(out)
                    bool = True
                    # print(out, "撞车了")
                    break
                station = b[:b.index(car)]
                b.remove(car)
                # print(f"{car}号小火车走了,站内还有{station}")
            if not bool:
                allc.append(" ".join(out))
        allc.sort()

        print("\n".join(allc))
    except:
        break



编辑于 2020-09-07 18:24:59 回复(0)
Python
鲸鱼要好好学习呀头像 鲸鱼要好好学习呀
看了题解和讨论区都是用传统的进出栈来求解的，我这里提出一种新的思路，运用递归的方法：
1）我们从对车的操作来考虑，构造一个对车进行操作的标记序列，例如[1,2,2,1]就代表1号车进站，2号车进站，2号车出站，1号车出站的一个操作流程，从这里我们不难看出，序列中第一次出现的序号代表该序号进站，第二次出现代表出站。
2）这里我们着重考虑最后一辆车进出站的情况，不难发现最后一辆车进站发生在前一辆进站之后的任意时刻都满足条件，而最后一辆车进站后由于没有车还能进站因此必须立即出站，因此在操作序列中，最后一辆车的序号必是连续的。
3）有了以上两点结论后我们便可以构造递归函数：
def cal(x,s):
    if x == 1:
        return [[s[0],s[0]]]    #只有一辆车时递归终止
    else:
        res = []
        for i in cal(x-1,s[0:x-1]):
            add = i.index(s[x-2])    #获得x-1辆车的操作序列中第x-1辆车编号第一次出现时的下标
            for j in range(add+1,len(i)+1):    #在第x-1辆车编号第一次出现之后的任意位置均可插入连续的第x辆车编号获得新序列
                temp = i[:]
                temp.insert(j,s[x-1])
                temp.insert(j,s[x-1])
                res.append(temp)
        return res
函数的输入参数x和s分别表示的是车的数量和进站的编号序列，递归的重点是车只有一辆时，只有进站出站一种排列方式，对于车有x辆时，由开头得出的两个结论，x辆车时的操作序列可以由x-1辆车时的操作序列中插入连续的第x辆车编号来获得。
现在我们得到了操作序列后我们需要由操作序列得到出站序列，显然我们只要把每辆车编号的第一次出现删除即可 
while True:
    try:
        n = int(input())
        sou = [int(x) for x in input().split()]
        ans = cal(n,sou)    #得到操作序列
        for i in ans:
            for j in range(1,n+1):
                i.remove(j)    #删除每辆车编号的第一次出现
        ans.sort()
        for i in ans:
            print(' '.join([str(x) for x in i]))
    except:
        break

编辑于 2020-08-15 14:30:56 回复(1)
Python
走:路头像 走:路

明晰易懂的递归实现

'''
栈  火车出站问题
恭喜你通过本题
运行时间：29ms
占用内存：3920k
'''
def station_scedule(wait_in, wait_out, leave):

    if (not wait_in) and (not wait_out):
        train_out.append(' '.join(leave))
    if wait_in:
        wait_in_ = wait_in[:]
        wait_out_ = wait_out[:]
        leave_ = leave[:]
        wait_out_.append(wait_in_.pop(0))
        station_scedule(wait_in_, wait_out_, leave_)
    if wait_out:
        wait_in_ = wait_in[:]
        wait_out_ = wait_out[:]
        leave_ = leave[:]
        leave_.append(wait_out_.pop())
        station_scedule(wait_in_, wait_out_, leave_)
while True:
    try:
        N, train_in = int(input()), input().strip().split(' ')
        train_out = []
        leave = []
        station_scedule(train_in, [], leave)
        for i in sorted(train_out):
            print(i)
    except:
        break
发表于 2020-07-20 16:08:19 回复(0)
Python
君临天下201804050931706头像 君临天下201804050931706
def func(l,inTrains,outTrains,res):
    if(len(l)==0 and len(inTrains)==0):
        res.append(outTrains)
    else:
        if inTrains:
            c_out = outTrains + inTrains[-1] + ' '
            func(l,inTrains[:-1],c_out,res)
        if l:
            c_in = inTrains.copy()
            c_in.append(l[0])
            func(l[1:],c_in,outTrains,res)

while True:
    try:
        num = int(input())
        trains = input().split()
        res = []
        func(trains.copy(), [], '', res)
        res.sort()
        for i in res:
            print(i)
    except:
        break
发表于 2020-07-12 15:24:40 回复(1)
Python
坚定的小饼干在投简历头像 坚定的小饼干在投简历
# 经典递归   a:进栈口 container:栈 b:出栈记录 b_list:保存出栈记录的列表

import copy

while True:
    try:
        num = input()
        a =input().split(" ")
        b_list = []
        def handel(a,container=[],b=""):
            if container==[] and a ==[]:
                b_list.append(b)
                return
            elif container == []:
                container.append(a.pop(0))
                handel(a,container,b)
            elif a == []:
                b += container.pop()
                handel(a,container,b)
            else:
                a1,container1 = copy.copy(a),copy.copy(container)
                container.append(a.pop(0))
                handel(a,container,b)

                b += container1.pop()
                handel(a1,container1,b)

        handel(a)
        b_list = sorted(b_list)
        for i in b_list:
            print(i.replace(""," ").strip())
    except:
        break

发表于 2020-06-10 19:22:15 回复(0)
提交观点

问题信息

栈
难度：
7条回答 39116浏览

热门推荐

通过挑战的用户

查看代码

相关试题

火车进站

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号