火车进站_算法排序和火车排序-CSDN博客

本文链接：https://blog.csdn.net/coder_lj/article/details/72772749

本文介绍了一个基于火车序列的算法问题，通过使用next_permutation生成所有可能的排列，并判断哪些是有效的出站序列。该问题利用了栈的数据结构来辅助判断过程，确保了出站序列的有效性和正确性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。

输入描述:

有多组测试用例，每一组第一行输入一个正整数N（0<N<10），第二行包括N个正整数，范围为1到9。

输出描述:

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

输入例子:

3
1 2 3

输出例子:

3 2 1

解题思路：

根据输入的序列调用next_permutation算法依次生成的全排列由函数IsPopOrder对其进行判断，如果是合法的出站序列，就进行输出。

判断函数内部算法：

对两个序列pushV和popV,对两者的元素依次进行比较，如果相等则指针依次往后，否则，先判断栈是否为空，若不为空，则判断栈顶元素与popV当前指针指向的元素是否相等，若不等，则将popV当前元素入栈，若等，则栈顶元素出栈。进行了这几步之后，判断还没有结束。因为栈里面可能还有元素需要比较。此时，对栈中元素依次与popV剩余元素进行比较，若等，则出栈，若不等，则直接返回false，最后若栈空，返回true。

#include<iostream>	//火车进站
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;

bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> s;
        int j=0;
        for(int i=0;i<pushV.size()&&j<popV.size();i++)
        {
            if(pushV[i]!=popV[j])
            {
                if(!s.empty())
                {
                    if(s.top()!=popV[j])
                        s.push(pushV[i]);
                    else
                        s.pop();
                }
                else
                    s.push(pushV[i]);
            }
            else
            {
                j++;
            }
        }
        while(!s.empty())
        {
            if(s.top()==popV[j++])
                s.pop();
            else
                return false;
        }
        return true;
    }

int main()
{
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    vector<int> vv=v;
    do{
        if(IsPopOrder(vv,v))
        {
            for(int i=0;i<n;i++)
            {
                if(i==n-1)
                    cout<<v[i]<<endl;
                else
                    cout<<v[i]<<" ";
            }
        }
    }while(next_permutation(v.begin(),v.end()));
    return 0;
}