火车进站

[编程题]火车进站

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

给定一个正整数N代表火车数量，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。

要求输出所有火车出站的方案，以字典序排序输出。

进阶：时间复杂度： $O(n!)\$ ，空间复杂度： $O(n)\$

输入描述:

第一行输入一个正整数N（0 < N < 10），第二行包括N个正整数，范围为1到10。

输出描述:

输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。

示例1

输入

3
1 2 3

输出

说明

第一种方案：1进、1出、2进、2出、3进、3出
第二种方案：1进、1出、2进、3进、3出、2出
第三种方案：1进、2进、2出、1出、3进、3出
第四种方案：1进、2进、2出、3进、3出、1出
第五种方案：1进、2进、3进、3出、2出、1出
请注意，[3,1,2]这个序列是不可能实现的。

算法知识视频讲解

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 回复(0)