列车车厢重排问题的两种解法

列车车厢重排问题的两种解法

引用

CSDN

1.

https://m.blog.csdn.net/bz_czq/article/details/136891726

列车车厢重排问题是一个经典的算法题，主要考察队列和优先队列的应用。本文将详细介绍这个问题的两种解法，从最朴素的模拟方法到优化的空间复杂度实现，帮助读者理解如何通过数据结构优化算法效率。

问题描述

列车车厢重排时，位于入轨道和出轨道之间的缓冲轨道按照FIFO方式运作，如下图所示，因此可将它们视为队列。禁止将车厢从缓冲轨道移到入轨道，或从出轨道移到缓冲轨道。所有的车厢移动都要按照图中箭头所示的方向进行。

第k条轨道Hk可直接将车厢从入轨道移到出轨道。其余 k-1 条轨道用来缓存不能直接进入出轨道的车厢。

假定有9节车厢需要重排，其初始顺序5、8、1、7、4、2、9、6、3。假设k=3(见图)。3号车厢不能直接进人出轨道，因为1号车厢和2号车厢必须排在3号车厢之前。因此，3号车厢进入缓冲轨道H1。6号车厢可进人缓冲轨道H1，排在3号车厢之后，因为6号车厢是在3号车厢之后进人出轨道。9号车厢可以继续进入缓冲轨道H1，排在6号车厢之后。2号车厢不可排在9号车厢之后，因为它必须在9号车厢之前进入出轨道。因此，2号车厢进入缓冲轨道H2.排在第一。4号车厢可以进人缓冲轨道H2，排在2号车厢之后。7号车厢也可进入缓冲轨道H2，排在4号车厢之后。这时，1号车厢可通过缓冲轨道 H3直接进入出轨道。接下来2号车厢从缓冲轨道H2进入出轨道，3号厢从缓冲轨道H1进入出轨道，4号车厢从缓冲轨道H2进人出轨道。由于5号车厢此时仍在入轨道上，且排在8号车厢之后，所以8号车厢进人缓冲轨道H2，这样5号车厢可以通过缓冲轨道H3，直接从入轨道进入出轨道。然后，6号7号、8号和9号车厢依次从缓冲轨道进入出轨道。

当一节车厢c进人缓冲轨道时，依据如下的原则来选择缓冲轨道:

• 如果缓冲轨道上已有的尾部车厢编号均小于c；且有多个缓冲轨道都满足这一条件，则选择左端车厢编号最大的缓冲轨道
• 否则选择一个空的缓冲轨道(如果有的话)

基本算法如下：

1. 分别对k个队列初始化；
2. 初始化下一个要输出的车厢编号nowOut = 1;
3. 依次取入轨中的每一个车厢的编号；
   3.1 如果入轨中的车厢编号等于nowOut，则
   3.1.1 输出该车厢；
   3.1.2 nowOut++；
   3.2 否则，考察每一个缓冲轨队列
   for (j=1; j<=k; j++)
   3.2.1 取队列 j 的队头元素c；
   3.2.2 如果c=nowOut，则
   3.2.2.1 将队列 j 的队头元素出队并输出；
   3.2.2.2 nowOut++；
   3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则
   3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;
   3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；

给定入轨道车厢的一个排列，输出至少需要的缓冲轨道数量。

输入形式

5 8 1 7 4 2 9 6 3

输出形式

3

样例输入

样例输出

样例说明

评分标准

注意

本题的输入方式不同于其它题，本题没有给出具体输入的数据的个数，所以只能使用while循环等不断循环输入直到读取到结束符^Z，也是EOF，在C++里是一个宏。如果要调试的话可以在输入之后再换行输入^Z。

解题思路分析

解法一

对于本题来说，我们最容易想到的便是直接模拟，采用最为朴素的算法，也就是创建一个队列数组，每个队列存放一个火车车厢排列。当判断第i个车厢是直接出去还是入队时，先依次判断每个排列的队首元素能否出去直到没有能出去的了，然后再判断该车厢，如果它的编号刚好等于newout就直接出去，否则将其编号与前面的所有火车车厢排列的队尾元素进行比较，加入编号小于其的最大编号的排列，如果没有小于其的排列，则加入新的排列。如此循环下去，总的排列数即为答案。

#include<iostream>
#include<queue> 
using namespace std;
queue<int> q[100];//此数组大小取决于车厢数
int cnt=0;//记录总队列数 
int num[1000];//储存车厢初始排列

int main()
{
    int x,size=0;//车厢数量 
    
    while(scanf("%d",&x)!=EOF)
    num[size++]=x;
    
    int newout=1;//当前可以直接出去的车厢编号 
    for(int i=size-1;i>=0;i--)//倒序遍历
    {
        
        for(int j=0;j<cnt;j++)
        {
            if(!q[j].empty())//如果第j个队列不为空 
            {
                if(q[j].front()==newout)
                {
                    newout++;
                    q[j].pop();//队首出队
                    j=-1;//有一个能出去的话整个缓冲轨道上的队列的队首元素都要重判
                         //赋值j=-1而非0是因为在循环体执行完后会执行j++
                }
            }
        } 
        
        if(num[i]==newout)//如果能直接出去 
        {
            newout++;
            continue;
        }
        
        if(cnt==0)//特判无车在列的情况 
        {
            q[cnt++].push(num[i]);
            continue;
        }
        
        //如果已有队列和当前车厢都不能出去
        int Max=0,index=0;
        int empty_loc=-1;//记录已经使用过的队列中任一为空的队列
        bool flag=0;//记录是否有小于当前车厢编号的队列末尾车厢
        
        for(int j=0;j<cnt;j++)//求取小于当前车厢编号的队列末尾车厢 
        {
            if(q[j].empty())
            {
                empty_loc=j;
                continue;
            }
            if(q[j].back()<num[i])
            {
                if(q[j].back()>Max)
                {
                    Max=q[j].back();
                    index=j;
                }
                
                flag=1;
            }
        }
        
        if(flag==1)
        {
            q[index].push(num[i]);
        }
        else
        {
            if(empty_loc!=-1) q[empty_loc].push(num[i]);
            else q[cnt++].push(num[i]);
        }
        
    } 
    
    cout<<(cnt+1); 
    return 0;
}  

解法二

解法一显然过于朴素，我们可以采取一点优化，我们知道，每次都只要将第i个车厢的编号与每个排列的尾部元素进行比较，因此我们可以直接用数组记录各个尾部元素，如此便优化了空间，不必开很多队列；同时，我们可以将入队的元素采用递增的顺序排列，这样每次判断排列中的车厢是否可以出去就不用依次循环比较了，只需从头开始比较就行了。实现递增可以使用优先队列，优先队列实现有序的时间复杂度是O(n*logn)，每一次添加新元素只需logn的时间。如此，便可以一种较快的方式解决该题。当然，还可以将尾部元素的排列变为有序的，使每次查找的时间变为logn，这样就更快了。

下面使解法二的代码：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int last[1000];
int len=0;
priority_queue<int,vector<int>,greater<int> > q;
int num[1000];
int main()
{
    int x,curr=1,size=0;
    
    while(scanf("%d",&x)!=EOF)
        num[size++]=x;
    
    for(int i=size-1;i>=0;i--)
    {
        x=num[i];
        if(x==curr)
        {
            curr++;
            continue;
        }
        if(len==0)
        {
            last[len++]=x;
            q.push(x);
            continue;
        }
        
        
        while(!q.empty() && q.top()==curr)
        {
            q.pop();
            curr++;
        }
        
        if(curr==x)
        {
            curr++;
            continue;
        }
        bool flag=0;
        int Max=0,index=0;
        for(int i=0;i<len;i++)
        {
            if(x>last[i])
            {
                if(last[i]>Max)
                {
                    Max=last[i];
                    index=i;
                }
                flag=1;
            }
        }
        q.push(x);
        
        if(flag==0)
        {
            last[len++]=x;
        }
        else
        {
            last[index]=x;
        }
        
    }
    cout<<(len+1);
     return 0;
}