L2_014列车调度(set)

image

两端分别是一条入口（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

---

• 思路
  对于每一辆车可以开入当前已有轨道中末尾车辆编号大于该量车的轨道，若没有，则新开一个轨道
  用一个数组来存每条轨道当前末尾的那辆车编号，每次用for循环来寻找可开入轨道，并更新编号数值
  双重for循环n^2超时
  而且我这样还无法保证每辆车都放在当前它可选位置中离他最近的那个位置

---

#include <iostream>
using namespace std;
int main()
{
    int num=0;
    int avec[100000];//存每条轨道当前最小的元素
    int n;cin>>n;
    for(int i=1;i<=n;++i){
        int x;cin>>x;
        int flag=0;
        for(int j=0;j<num;++j){
            if(x<avec[j]){
                //注意题目要求的是大的先出所以轨道中是小的排后面
                avec[j]=x;
                flag=1;
                break;//注意找到了就要break不然后面又遇到比它小的又要赋值就乱了
            }
        }
        if(!flag){
            avec[num]=x;
            ++num;
        }
    }
    cout<<num;
    return 0;
}

---

• 为了尽可能利用轨道，新来的车辆应该开入编号离他最近的那个轨道，比如1应该放入2后面而不是5后面
  而且for循环寻找很耗时
  可以用本身就排好序，寻找操作高效的set来做
  新来一辆车就利用upper_bound方法找到第一个编号大于它的轨道，erase这个位置上的元素，在insert新编号，若新来的编号大于set里的最大值，则直接insert这个编号
  注意开始要insert一个0，便于第一个新编号的insert，但最后结果记得减1
  参考：https://www.liuchuo.net/archives/1967

---

#include <iostream>
#include <set>
using namespace std;
int main()
{
    int n;cin>>n;
    set<int> s;
    s.insert(0);
    for(int i=1;i<=n;++i)
    {
        int x;cin>>x;
        if(x>*(--s.end())){
            //要写--不能写-1没有重载减号
            s.insert(x);
        }else{
        set<int>::iterator it=s.upper_bound(x);
        s.erase(it);
        s.insert(x);
        }
    }
    cout<<s.size()-1;
    return 0;
}