PTA L2-014 列车调度（25分）

柔情只为你懂 2023-09-25 18:26 10阅读 0赞

火车站的列车调度铁轨的结构如下图所示。

![cc6cbb5f96994e7fa023651e2b7e7bf9.jpeg][]

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照\{8，4，2，5，3，9，1，6，7\}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

### **输入格式：** ###

输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

### **输出格式：** ###

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

### **输入样例：** ###

9
    8 4 2 5 3 9 1 6 7

### **输出样例：** ###

> 吐槽：

刚开始看到这题的时候一头雾水，想了老半天也不晓得4是咋来的。在我的一顿“死缠烂打”下，终于还是将这个题目给啃明白了。

因为该题用到了C++中的关于set关联容器的一些操作（其实set就是集合的意思），所以我先给大家补充一些关于set的用法，方便大家可以更好的去理解代码。

insert() //插入元素到集合中
    size() //返回集合中元素的个数
    erase()//删除集合中的某个元素
    rbegin()//反向迭代器,指向容器中最后一个元素的迭代器，迭代器可以理解为C语言里面的指针哈
    lower_bound()//第一个大于等于某个值的元素的迭代器
    upper_bound()//第一个大于某个值的元素的迭代器

值得一说的是，set集合中的元素会自动按从小到大的顺序排列，并且具有互异性（不会出现两个相同的元素），这个大家应该都能懂吧，高中数学应该都学过吧。

> 思路：

这道题要求输入的列车序号按降序输出的话需要借助几条平行铁轨完成，以题目所给的输入样例为例，输出结果4是这样来的：

1 2 4 8

3 5

6 9

怎么来的呢？

就是把每个列车序列号放入在比某条轨道中最后面的序列号（元素）大最少的轨道中，如果没有的话就重新开辟一条新的轨道用于调度。

这么说可能有点抽象哈，那么咋们来一步一步来实现看看：

刚开始列车序号的排序是  8 4 2 5 3 9 1 6 7

首先我们先开辟一条新的轨道放8号进去

然后是4号，4比8小所以在同一条轨道里边

4 8

2比4小，所以还在同一条轨道

2 4 8

到5号的时候因为5大于2所以另开一条轨道让5进去

2 4 8

再往后3大于2小于5所以不进第一条轨道进入第二条轨道

2 4 8

3 5

再再往后是9比2大，也比3大，所以再开一条新的轨道让它进去

2 4 8

3 5

再再再往后是1比2小也比3小但是更接近2所以进入第一条轨道

1 2 4 8

3 5

再再再再往后就是6啦它只比9小所以进入第三条轨道

1 2 4 8

3 5

6 9

最后的7比1、3、6都大所以又要另开一条轨道

1 2 4 8

3 5

6 9

这样一步一步下来大家应该都能理解了吧，如果还不懂的话就再多看几遍哈。

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        cin>>n;
        set<int>gather;
        gather.insert(-1);    
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            if(x< *gather.rbegin())
            {    
                gather.erase(*(gather.upper_bound(x)));    
            }
            gather.insert(x);    
        }
        cout <<gather.size()-1<< endl;    
    }

这里怕大家还是看不懂就在稍微讲解一下哈，前面说啦rbegin（）是指向集合中最后一个元素的迭代器，相当于C语言中的指针，所以前面加了个\*代表了该位置所代表的数据。

[cc6cbb5f96994e7fa023651e2b7e7bf9.jpeg]: https://img-blog.csdnimg.cn/img_convert/cc6cbb5f96994e7fa023651e2b7e7bf9.jpeg