首页 > 试题广场 >

火车进站

[编程题]火车进站

热度指数：86049 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 火车站一共有 $n$ 辆火车需要入站，每辆火车有一个编号，编号为 $1$ 到 $n$ 。
$\hspace{15pt}$ 同时，也有火车需要出站，由于火车站进出共享一个轨道，所以后入站的火车需要先出站。换句话说，对于某一辆火车，只有在它之后入站的火车都出站了，它才能出站。

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

输入描述:

第一行输入一个整数  代表火车的数量。
第二行输入  个整数  代表火车的入站顺序。

输出描述:

输出若干行，每行输出  个整数，代表一种出站顺序。你需要按照字典序从小到大依次输出。

示例1

输入

3
1 2 3

输出

说明

在这个样例中，每一种出栈顺序的详细出入站状况为（黑色普通字体代表入站、橙色加粗字体代表出站）：
；
；
；
；
。

算法知识视频讲解

Python3

newMar

while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))

        result = []
        # 待办事项列表：记录所有要尝试的情况
        todo = [(nums, [], [])]  # 格式：(等待进站的车, 站台上的车, 已出站的车)
        
        while todo:  # 还有情况要尝试
            wait, station, out = todo.pop()  # 取出一个情况
            # 如果所有车都处理完了，记录结果
            if not wait and not station:
                result.append(" ".join(map(str, out)))
            # 尝试"出站"操作
            if station:
                # 站台最外面的车出站
                todo.append((wait, station[:-1], out + [station[-1]]))
            # 尝试"进站"操作
            if wait:
                # 最前面的车进站
                todo.append((wait[1:], station + [wait[0]], out))

        # 输出所有可能的结果
        for i in sorted(result):
            print(i)
    except:
        break

发表于 2025-11-26 14:30:02 回复(0)

Python3

君心如梦

#我觉得我的思路应该是最直观容易想象的。对于n个火车，一定有2n个操作，第一个肯定是进站，最后一个肯定是出站。那我只需要生成一个2n-2长度的二进制字符串，其中0代表接下来进站一辆，1代表接下来出站一辆。同时保证从前到后遍历字符串时候，0总是大于等于1的。那么接下来就按照字符串进行进栈出栈操作就好。最后将得到的结果用sorted函数排序，输出即可。

n = int(input())

ray = list(map(int, input().split()))

monilist = []

# 生成所有合法序列

for i in range(0, 2 ** (2*n - 2)):

k = str(bin(i)[2:]).zfill(2*n - 2)

if k.count('1') == n - 1:

k = '0' + k + '1'

# 检查所有前缀（包括整个序列）

for p in range(1, len(k) + 1):

tstr = k[:p]

if tstr.count('0') < tstr.count('1'):

break

else:

monilist.append(k)

# 模拟栈操作

finlist = []

for seq in monilist:

zanlist = ray.copy() # 重置待处理列表

inslist = [] # 重置栈

outslist = [] # 重置输出

for op in seq:

if op == '0':

inslist.append(zanlist.pop(0))

else:

outslist.append(inslist.pop())

finlist.append(outslist)

# 按字典序排序并输出

for seq in sorted(finlist):

print(' '.join(map(str, seq)))

发表于 2025-05-20 21:21:54 回复(0)

Python3

doumihuoguo

参考评论区大佬的解法

先用itertools产生所有可能的排序，再定义一个函数来判断每个排序方法是否能实现

函数思路：

依次进栈，每进栈一次就判断和拟出栈火车是否相同，相同则出栈，不同则继续进栈第二辆。在所有进栈和拟出栈完毕后判断栈是否为空，空的说明能实现

import itertools
n = int(input())
l = input().split()
l1 = itertools.permutations(l)
l2 =  sorted(l1)
def isvalid(ll, l0):
    stack = []
    for i in l0:
        stack.append(i)
        for j in ll[:]:
            if j == stack[-1]:
                stack.pop()
                ll.remove(j)
                if not stack:
                    break
            else:
                break
    if not stack:
        return True
    else:
        return False
for i in l2:
    if isvalid(list(i), l):
        print(' '.join(i))

发表于 2024-12-19 15:35:29 回复(2)

Python3

牛客175499463号

#!/user/local/bin/python3

TrainNum=int(input())
TrainIDlist=list(map(int,input().split()))

train_id_list=[[item,0,0] for item in TrainIDlist]
#第二列表示当前火车的第一个排列组合在matrix里面的行索引
#第三列表示当前火车的最后一个排列组合在matrix里面的列索引

matrix=[[0 for j in range(TrainNum*2)]]
matrix[0][0]=TrainIDlist[0]
matrix[0][1]=TrainIDlist[0]
train_id_list[0][1]=0
train_id_list[0][2]=0

##迭代计算所有排列组合
for i in range(1,TrainNum):
    upp_train_id=TrainIDlist[i-1]
    train_id=TrainIDlist[i]
    fcombin_index=train_id_list[i-1][1]   #上一辆火车的第一个排列组合在matrix里面的行索引
    lcombin_index=train_id_list[i-1][2]   #上一辆火车的最后一个排列组合在matrix里面的行索引
    train_id_list[i][1]=train_id_list[i-1][2]+1
    for j in range(fcombin_index,lcombin_index+1):
        upp_in_index=matrix[j].index(upp_train_id)  #上一辆火车进场以后，当前火车马上进场马上出场，所有的位置都可以插入
        for p in range(upp_in_index,i*2):
            matrix.append(matrix[j].copy())       
            nRowIndex=len(matrix)-1
            matrix[nRowIndex][p+1]=train_id
            matrix[nRowIndex][p+2]=train_id
            newindex=p+3
            while newindex<i*2+2:
                matrix[nRowIndex][newindex]=matrix[j][newindex-2]
                newindex+=1
    train_id_list[i][2]=len(matrix)-1

resultList=[]
for x in range(train_id_list[TrainNum-1][1],len(matrix)):   #去掉matrix里面的进站信息，只保留出站信息
    resultList.append(matrix[x].copy())
    for id in TrainIDlist:
        resultList[-1].remove(id)
resultList.sort()

for item in resultList:
    print(" ".join(map(str,item)))

发表于 2024-12-15 22:00:34 回复(0)

Python3

呆呆的鱼游

import copy

# 比较清晰，简单，好理解的方法，看讨论比较少，补充一个

total_num = int(input().strip())

all_train_list = input().strip().split(" ")

list_set = set()

ans_set = set()

def do_work(in_list=[], out_list=[]):

# 如果都已经全部安排好了，可以打印出来

if len(in_list) == total_num and len(out_list) == total_num:

ans_set.add(" ".join(out_list))

return []

# 对于重复安排的过滤

list_new_str = " ".join(in_list) + "+" + " ".join(out_list)

if list_new_str in list_set:

return

list_set.add(list_new_str)

in_list_new = copy.deepcopy(in_list)

out_list_new = copy.deepcopy(out_list)

# 可以选择第一个火车进

for train in all_train_list:

if train not in in_list:

in_list_new.append(train)

do_work(in_list_new, out_list_new)

in_list_new = copy.deepcopy(in_list)

out_list_new = copy.deepcopy(out_list)

# 可以选择最后一个进的的火车出

if in_list:

for train in in_list[::-1]:

if train not in out_list:

out_list_new.append(train)

do_work(in_list_new, out_list_new)

do_work()

ans_list = list(ans_set)

ans_list.sort()

for ans in ans_list:

print(ans)

发表于 2024-12-04 11:20:39 回复(0)

Python3

牛客947768359号

# dfs结合栈
import sys
from collections import deque

def dfs(in_stack, out_stack, current_out):
    # in_stack 还没进站的车  out_stack 已经进站但还没出栈的车    current_out 当前的出站序列
    if not in_stack and not out_stack:
        record.append(current_out)
        return
    if in_stack:
        dfs(in_stack[1:], out_stack+[in_stack[0]], current_out)
    
    # 出站操作：如果栈中有火车可以出站
    if out_stack:
        dfs(in_stack, out_stack[:-1], current_out + [out_stack[-1]])

    

data = sys.stdin.read().splitlines()
trian_list = list(map(int,data[-1].split()))
record = []
# print(trian_list)
dfs(trian_list,[],[]) 
record = sorted(record)
for r in record:
    print(*r)

发表于 2024-09-25 01:50:11 回复(0)

Python3

九天揽月a

"""
栈的出栈序列排列问题”或称“卡特兰数问题”：
给定一个数组，该数组中的元素依次入栈。在入栈的过程中，允许在任意时刻进行出栈操作。
问题是：通过这些入栈和出栈操作，最后得到的出栈序列有哪些可能？以及有多少种可能的出栈序列？
使用递归回溯法
"""


def generate_stack_permutations(seq):
    n = len(seq)

    # 存储所有可能的出栈序列
    results = []

    # 递归函数来模拟栈操作
    """该递归函数会造成算力浪费"""

    def backtrack(input_seq, stack, output_seq):
        # 如果整个序列都已入栈并且栈已空，则输出序列是完成的
        if not input_seq and not stack:
            results.append(output_seq[:])
            return

        # 如果输入序列还有元素可入栈
        """
        本步完成了一次输入序列的单元素入栈操作，并对剩下的序列继续调用函数
        最后移除刚刚入栈的元素，回溯到原先的状态
        """
        if input_seq:
            # 模拟入栈操作
            stack.append(input_seq[0])
            backtrack(input_seq[1:], stack, output_seq)
            """回溯法"""
            stack.pop()  # 删除stack最后一个，回溯入栈操作

        # 如果栈中有元素可出栈
        if stack:
            # 模拟出栈操作
            popped = stack.pop()  # 出栈一个元素
            output_seq.append(popped)  # 加入输出序列
            backtrack(input_seq, stack, output_seq)  # 递归
            output_seq.pop()  # 回溯，移除刚加入的元素
            """回溯法"""
            stack.append(popped)  # 回溯堆栈状态

    # 开始递归
    backtrack(seq, [], [])
    return results


n = input()
input_sequence = [int(i) for i in input().split(' ')]
all_permutations = generate_stack_permutations(input_sequence)

# 输出所有可能的出栈序列，字典序排序
all_permutations = sorted(all_permutations)
for permutation in all_permutations:
    print(" ".join([str(i) for i in permutation]))

# 输出总数量
# print("总出栈序列数量:", len(all_permutations))

编辑于 2024-08-30 12:29:24 回复(0)

Python3

yangyeji

from functools import cmp_to_key

import copy

def paix(x):

if len(x) == 1:

return [x]

a_end = []

zhan = []

for i in range(0, len(x)):

# 入栈部分都在zhan里

zhan.append(x[i])

# 对没入栈的那部分递归

b = [j for j in x[i+1:]]

a = paix(b)

for j in range(len(a)):

zhan1=copy.deepcopy(zhan)

zhan1.reverse()

a1=copy.deepcopy(a[j])

a1 = a1 + zhan1

a_end.append(a1)

# 让入栈的部分出栈

if i == len(x) - 1:

zhan.reverse()

a_end.append(zhan)

continue

a2 = paix(zhan)

a_end2 = [i2 + j2 for i2 in a2 for j2 in a]

a_end += a_end2

# qucong

b_end=[]

for i in a_end:

if i not in b_end:

b_end.append(i)

return b_end

def pan(x1,x2):

for i in range(0,len(x1)):

if x1[i]!=x2[i]:

return x1[i]-x2[i]

n = int(input())

x = list(map(int, input().split()))

mmap = paix(x)

mmap.sort(key=cmp_to_key(pan))

for i in mmap:

out=""

for j in i:

out=out+str(j)+" "

print(out)

发表于 2023-08-23 18:11:14 回复(0)

Python3

1bit都不剩了

def updateTrainExitSequence(train_outside,train_inside,all_exit_way,exit_way_arr):
    if(train_outside):
        enter_train = train_outside.pop(0)
        train_inside.append(enter_train)
        updateTrainExitSequence(train_outside,train_inside,all_exit_way,exit_way_arr)
        train_inside.pop()
        train_outside.insert(0,enter_train)
    if(train_inside):
        exit_train = train_inside.pop()
        exit_way_arr.append(exit_train + " ")
        updateTrainExitSequence(train_outside,train_inside,all_exit_way,exit_way_arr)
        exit_way_arr.pop()
        train_inside.append(exit_train)
    if(not train_outside and not train_inside):
        all_exit_way.append("".join(exit_way_arr))


train_num = int(input())
train_outside = input().split()
all_exit_way = []
updateTrainExitSequence(train_outside,[],all_exit_way,[])
all_exit_way.sort()
for exit_way in all_exit_way: print(exit_way)

发表于 2023-07-28 15:23:47 回复(0)

Python3

有趣的代码渣渣在吐槽

    该代码核心思想参考其它大神(并非自创)，我这边大概写一下我理解的思路
    n, nums = input(), input().split()
    res = []
    def dfs(w, i, o):

        # 如果没有 待需要进栈的火车 和 需要出栈的火车，证明所有火车都已出栈
        # 需要将都已出栈的火车添加到res
        if not w and not i:
            res.append(' '.join(map(str, o)))

        # 如果有 待需要进栈的火车，那么则安排一辆火车进栈
        if w:
            dfs(w[1:], i + [w[0]], o)

        #如果有进栈的火车，那么可以安排火车出栈
        if i:
            dfs(w, i[:-1], o + [i[-1]])
    dfs(nums, [], [])

    #sorted 按照题目要求，字典序输出
    for i in sorted(res):
        print(i)

发表于 2023-05-05 22:44:31 回复(2)

Python3

AlfredP

n=input().strip()
in_order=input().strip().split(' ')
res=[]

def in_out(station,waiting,out_station):
    if waiting:
        in_out(station+[waiting[0]],waiting[1:],out_station)
    if station:
        in_out(station[:-1],waiting,out_station+[station[-1]])
    if not station and not waiting:
        res.append(out_station)

in_out([],in_order,[])
res.sort()
for i in res:
    print(*i)

发表于 2023-05-04 13:39:17 回复(0)

Python3

再多看一眼就会爆炸

n=int(input())
x=list(map(str,input().split()))
rem=[]
def ways(x=[],s=[],o=[]):
    if x==[] and s==[]:
        rem.append(o)
    if x:
        ways(x[1:],s+list(x[0]),o)
    if s:
        ways(x,s[:-1],o+list(s[-1]))

ways(x)
rem=list(sorted(rem))
for i in rem:
    print(*i)

发表于 2023-03-10 01:11:44 回复(0)

Python3

O_t真

n = input()
ss = input().split()
ss.reverse()
ou = []
def cel(s, i, o):
    if not s and not i:
        ou.append(o)     
        return 
    if s:
        on = o.copy()
        sn = s.copy()
        sn.pop()
        inew = i.copy()
        inew.append(s[-1])
        cel(sn, inew, on)
    if i:
        on = o.copy()
        sn = s.copy()
        inew = i.copy()
        inew.pop()
        on.append(i[-1])
        cel(sn, inew, on)

cel(ss, [], [])

ou.sort()
for i in ou:
    for j in i:
        print(j, end=' ')
    print('')

发表于 2023-03-06 14:45:16 回复(0)

Python3

在做的机考肯定是必过呀

#此题动态规划解题，等候入站的序列和出站的序列不为空都会有
对应的入站和出站，边界为两者都为空时，将此时用于装出站序列的out列表
加入到出站方案列表中。
def trail(wait,stack,out):
    if not wait and not stack:#边界
        l.append(' '.join(map(str,out)))
    else:
        if wait:#入站
            trail(wait[1:],stack+[wait[0]],out)
        if stack:#出站
            trail(wait,stack[:-1],out+[stack[-1]])


while True:
    try:
        l = []
        n = int(input())
        wait = list(map(int,input().split()))
        trail(wait,[],[])
        l = sorted(l)#排序
        for i in l:
            print(i)
    except:
        break

发表于 2023-02-27 13:20:26 回复(0)

Python3

ssssuperstone

1、只有一辆车，一种方式

2、多辆车，分成两部分思考：
①前面的部分先进出完毕，后面的部分再进出完毕，

②前面的部分先进，后面的部分进出完毕后前面的再按顺序出

3、去重

4、排序

n=int(input())
s=list(map(int,input().split(' ')))

def inout(l:list):
    myl=[]
    if len(l)==1:
        myl.append(l)
    else:
        for i in range(1,len(l)):
            l1=inout(l[:i])
            l2=inout(l[i:])
            tmp=l[:i][::-1]
            for i in l1:
                for j in l2:
                    k=i+j
                    if k in myl:
                        continue
                    else:
                        myl.append(k)
            for j in l2:
                k=j+tmp
                if k in myl:
                    continue
                else:
                    myl.append(k)
    return(myl)

out=inout(s)
out=sorted(out)
for i in out:
    i=list(map(str,i))
    print(' '.join(i))

发表于 2023-02-17 16:16:07 回复(0)

Python3

想转码的机械师

真太难了，我麻瓜看不懂，看了一个多小时才理清楚了逻辑，一开始实在不理解递归return返回到哪里，运行里面没有break，没有循环如何做到一遍又一遍append结果。我的理解是套娃里面再套小娃：每次运行到站内为0 和出站都套娃一遍函数，然后检测到站内为最后一个火车就开始return，直接return到上一次出站，接着入站，反反复复的，有种反复横跳的感觉，最后返回完所有函数结束。所以函数运行了一遍，但又运行了n遍。

小白答案都得看几十遍
while True:
    try:
        n = int(input())
        trains = input().strip().split(" ")
        res = []

        def rec_trains(cur_index, in_trains, out_trains):
            # 最后一个火车已经入站，此时只能出站
            print( cur_index,in_trains,out_trains,'/')
            
            if trains[-1] in in_trains:
                res.append(" ".join(out_trains + in_trains[::-1]))
                # print(res,cur_index)
                return
            # 没有火车入站，此时只能入站
            elif in_trains == []:
                rec_trains(cur_index + 1, in_trains + [trains[cur_index]], out_trains)
            else:
                # 出站，当前车站的最后一个火车出战
                rec_trains(cur_index, in_trains[:-1], out_trains + [in_trains[-1]])
                # print(cur_index)
                # 入站，当前的火车入站
                rec_trains(cur_index + 1, in_trains + [trains[cur_index]], out_trains)

        rec_trains(0, [], [])
        res.sort()
        print("\n".join(res))
    except:
        break

发表于 2023-01-29 03:23:27 回复(1)

Python3

牛客479609162号

n, a = int(input()), list(map(int, input().split()))
a.sort()#未进站
b = [] #已进站
c = [] #已出站
def enters(a,b,c):#进站
b = b + [a[0]] #防止覆盖变量
a = a[1:]
states(a,b,c)
def exits(a,b,c):#出站
c = c + [b[-1]]
b = b[0:-1]
states(a,b,c)
def states(a,b,c):
if len(c) == n:
for i in c:
print(i, end=" ")
print()
elif len(b) == 0:
enters(a,b,c)
elif len(a) == 0:
exits(a,b,c)
else:
exits(a,b,c)
enters(a,b,c)
states(a,b,c)

发表于 2021-12-09 18:00:08 回复(1)