7-10 列车调度

分数 25

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

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

输入格式：

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

输出格式：

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

输入样例：

1 2	9 8 4 2 5 3 9 1 6 7

输出样例：

代码长度限制

16 KB

时间限制

300 ms

内存限制

64 MB

这题思维量不大，火车在调度站的排列和蜘蛛纸牌类似，每一列必须维持大序号的列车在前面。如果新一列车对于所有的调度铁轨尾车号要大，就新开一个铁轨。

很容易发现，即使是最下面的是N号车厢，或者连续的N到N-M号车厢，并不会影响调度铁轨的数量。所以无需考虑。同时还很容易发现，新插入的列车如果小于多列调度铁轨尾车序号，应该选择与其序号相差最小的调度铁轨。

我最开始的思路是维护一个数组和一个size变量，分别存储每列车的最后一辆车的序号和调度铁轨的最小数量，但是在插入的过程中需要遍历所有的轨道进行比较，时间复杂度过高最终导致超时。

再进一步，我考虑到了sort排序进行维护，没有实现

最终采用的方法是维护一个set

#include <bits/stdc++.h>
#define mm(a) memset(a, 0, sizeof(a))
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, temp;
    cin >> N;N--;
    set<int> s;
    cin>> temp;
    s.insert(temp);
    while (N--) {
        cin >> temp;
        if(temp < *s.rbegin()){
            s.erase(s.upper_bound(temp));
        }
        s.insert(temp);
    }
    cout << s.size();
    return 0;
}

set会内部会自动维护一个红黑树，相对更高效，只需比较新插入的列车和set的尾部量（最大量rbegin()）的比较，如果更大就插入新值，如果已经有更大的量，就删除一个最小的比新插入的量大的量upper_bound()然后插入目前的列车（实际就是模拟了最新的列车替代了之前的列车）。

Set

引用C++ STL总结 | 行码棋 (wyqz.top)

7 set

7.1 介绍

set容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且set容器里的元素自动从小到大排序。

即：set里面的元素不重复且有序

//头文件
#include<set>
//初始化定义
set<int> s;

Cpp

7.2 函数方法

代码	含义
`s.begin()`	返回set容器的第一个元素的地址（迭代器）O(1)�(1)
`s.end()`	返回set容器的最后一个元素的下一个地址（迭代器）O(1)�(1)
`s.rbegin()`	返回逆序迭代器，指向容器元素最后一个位置O(1)�(1)
`s.rend()`	返回逆序迭代器，指向容器第一个元素前面的位置O(1)�(1)
`s.clear()`	删除set容器中的所有的元素,返回unsigned int类型O(N)�(�)
`s.empty()`	判断set容器是否为空O(1)�(1)
`s.insert()`	插入一个元素
`s.size()`	返回当前set容器中的元素个数O(1)�(1)
`erase(iterator)`	删除定位器iterator指向的值
`erase(first,second）`	删除定位器first和second之间的值
`erase(key_value)`	删除键值key_value的值
查找
`s.find(element)`	查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器
`s.count(element)`	查找set中的元素出现的个数，由于set中元素唯一，此函数相当于查询element是否出现
`s.lower_bound(k)`	返回大于等于k的第一个元素的迭代器O(logN)�(��)
`s.upper_bound(k)`	返回大于k的第一个元素的迭代器O(logN)�(��)

7.3 访问

迭代器访问

1 2	for(set<int>::iterator it = s.begin(); it != s.end(); it++) cout << *it << " ";

智能指针

1 2	for(auto i : s) cout << i << endl;

访问最后一个元素

1 2	//第一种 cout << *s.rbegin() << endl;

 //第二种
set<int>::iterator iter = s.end();
iter--;
cout << (*iter) << endl; //打印2;

1 2	//第三种 cout << *(--s.end()) << endl;

7.4 重载<运算符

基础数据类型

方式一：改变set排序规则，set中默认使用less比较器，即从小到大排序。（常用）

1 2	set<int> s1; // 默认从小到大排序 set<int, greater<int> > s2; // 从大到小排序

方式二：重载运算符。（很麻烦，不太常用，没必要）

//重载 < 运算符
struct cmp {
    bool operator () (const int& u, const int& v) const
    {
       // return + 返回条件
       return u > v;
    }
};
set<int, cmp> s; 

for(int i = 1; i <= 10; i++)
    s.insert(i);
for(auto i : s)
    cout << i << " ";
// 10 9 8 7 6 5 4 3 2 1

方式三：初始化时使用匿名函数定义比较规则

set<int, function<bool(int, int)>> s([&](int i, int j){
    return i > j; // 从大到小
});
for(int i = 1; i <= 10; i++)
    s.insert(i);
for(auto x : s)
    cout << x << " ";

高级数据类型（结构体）

直接重载结构体运算符即可，让结构体可以比较。

struct Point
{
    int x, y;
    bool operator < (const Point &p) const
    {
        // 按照点的横坐标从小到大排序,如果横坐标相同,纵坐标从小到大
        if(x == p.x)
            return y < p.y;
        return x < p.x;
    }
};

set<Point> s;
for(int i = 1; i <= 5; i++)
{
    int x, y;
    cin >> x >> y;
    s.insert({x, y});
}    
/* 输入
5 4
5 2
3 7
3 5
4 8
*/

for(auto i : s)
    cout << i.x << " " << i.y << "\n";
/* 输出
3 5
3 7
4 8
5 2
5 4
*/

7.5 其它set

multiset:元素可以重复，且元素有序
unordered_set ：元素无序且只能出现一次
unordered_multiset ：元素无序可以出现多次

莱蒙黎梦

从列车调度学习STL集合Set