首页 > 试题广场 >

火车进站

[编程题]火车进站

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

3
1 2 3

输出

说明

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

算法知识视频讲解

Jackn

#include <stdio.h>

int num_seq[10];
int use[10]={0};
int b[10];       //数组b，传入火车序号，得到火车位置（从1开始）

int f2(int n,int loc_seq[]){      //  f2()判断入站序列（实际位置序列）是否合法
    int st[n];
    int top=-1,i,max=0;
    for(i=0; i<n; i++){
        if(top==-1||loc_seq[i]>st[top]){
            for(int j=max+1; j<loc_seq[i]; j++)
                st[++top]=j;
            max=loc_seq[i];
        }
        else if(st[top]==loc_seq[i]) top--;
        else return 0;
    }
    return 1;
}

void f3(int n,int loc_seq[]){
    for(int i=0; i<n; i++)
        loc_seq[i]=b[num_seq[i]];
}

void f1(int n,int pos){

    if(pos==n) {
        int loc_seq[n];
        f3(n,loc_seq);
        if(f2(n,loc_seq))
        {
            for (int i = 0; i < n; i++)
                printf("%d ", num_seq[i]);
            printf("\n");
        }
        return;
    }
    for(int i=0; i<n ;i++){
        if(use[i]) continue;
        use[i]=1;
        num_seq[pos]=i+1;
        f1(n,pos+1);
        use[i]=0;
    }
}



int main() {
    int n,tmp;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d",&tmp);
        b[tmp]=i+1;
    }
    //首先实现全排列,用函数f1()
    f1(n,0);

    return 0;
}
写了第二遍才写好

发表于 2023-05-05 18:53:07 回复(1)