首页 > 试题广场 >

火车进站

[编程题]火车进站

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

3
1 2 3

输出

说明

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

算法知识视频讲解

Javascript_V8

徐海超201812091924948

// 要出来/要进去都没了 - 完成
// 要出来的没了 - 必须进去
// 要进去的没了 - 必须出来
// 进去/出来
while(n = +readline()) {
//     const items = readline().split(' ').map(Number);
    const res = [];
    const stack = []; // 进站
    let queue = []; // 待进站
    queue = readline().split(' ').map(Number);
//     getNT(items).map(item => console.log(item.join(' ')));
    function operate(stack, queue, out, n) {
        if (out.length == n*2 - 1) { // 全出来了
            res.push(out);
        } else if(queue.length && !stack.length) { // 没了 - 进入
            const inItem = queue.slice(0, 1); // 进站
            const addStack = [...stack, inItem];
            const newQueue = queue.slice(1);
//             console.log('in', addStack, newQueue, out, n);
            operate(addStack, newQueue, out, n);
        } else if (!queue.length && stack.length) { // 没要进去的了 - 必须有出来的
            const outItem = stack.slice(-1); // 出战
            const addOut = out.length ? out + ' ' + outItem : outItem;
            const newStack = stack.slice(0, stack.length - 1);
            operate(newStack, queue, addOut, n);
        } else { // 可以先进去 || 可以先出来
            const inItem = queue.slice(0, 1); // 进站
            const addStack = [...stack, inItem];
            const newQueue = queue.slice(1);
            operate(addStack, newQueue, out, n);
            const outItem = stack.slice(-1); // 出战
            const addOut = out.length ? out + ' ' + outItem : outItem;
            const newStack = stack.slice(0, stack.length - 1);
            operate(newStack, queue, addOut, n);
        }
    }
//     console.log('111', stack, queue, [], n)
    operate(stack, queue, '', n);
    
    res.sort();
//     console.log(res);
    res.map(item => console.log(item))
}

发表于 2022-04-07 19:15:19 回复(0)

Javascript_V8

我走路带風

let n;
while(n = readline()){
    var trains = readline().split(" ")
    var max = []
    var wuwu = function(num,list,arriving){
        if(num<trains.length){
            var list2 = list
            var arriving2 = arriving
            if(list.length>0){
               wuwu(num,list.slice(0,list.length-1),arriving+list[list.length-1]) 
            }
            
            wuwu(num+1,list+trains[num],arriving2)
        }else{
             for(let i =list.length-1;i>=0;i--){
                 arriving += list[i]
             }
            max.push(parseInt(arriving))
        }
    }
    wuwu(0,"","")
    
    max = max.sort(function(a,b){return a-b})
    
    for(let i =0;i<max.length;i++){
        let zf = max[i].toString().split("")
        let zz = ""
        for(let j=0;j<n;j++){
            zz += zf[j] + " "
        }
        console.log(zz.slice(0,2*n-1))
    }
}

发表于 2021-12-05 21:21:33 回复(0)