7-6 列车调度 (25 分)

时间:2024-03-24 12:25:35

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

7-6 列车调度 (25 分)

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

输入格式:

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

输出格式:

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

输入样例:

9
8 4 2 5 3 9 1 6 7

输出样例:

4

 最初思路:弄一个Vector二维数组,j=0,把第一个放进v[0]中,然后第二个看是不是比v[0]最后一个元素小,小的话就放进v[0]。                      不小的话j++,放进v[j]。再输入元素,从v[0]......v[j],判断哪个的最后一个元素小于我们输入的元素,就放进去,没有                      小于的   就j++,放到v[j]中;最后输出j+1;以为里面套了一层循环,时间复杂度为O(n^2);超时了;所以,就找大牛代                      码看,发现用的是set;

解题思路:
        先将一个数插入进set容器中,set容器默认从小到大(自动排序),在依次进行每个数的输入,如果输入的数比当前set容器中的最          后一个数小,删除set容器中第一个大于输入数的值,在将输入数进行插入,重新排序后,输入的值就代替了删除的值,依次          循环往复,进行到结尾 。

#include<iostream>
#include<set>
using namespace std;
int main()
{
    int num,n;
    cin>>n;
    set<int> s;
//    set<int>::iterator it;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(s.upper_bound(num)!=s.end())
            s.erase(s.upper_bound(num));
        s.insert(num);
//        for(it=s.begin();it!=s.end();it++){
//            cout<<*it<<" ";
//        }
//        cout<<endl;
    }
    cout<<s.size()<<endl;
    return 0;
}

看一下中间测试(吧上面的注释取消,既能看到每步的情况) ;

7-6 列车调度 (25 分)