巧用set容器

短命女 2022-09-30 12:54 206阅读 0赞

# L2-014. 列车调度 #

时间限制

300 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

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

![lp_o9wf01q8p76.jpg][]  
Figure

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

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <set>
    using namespace std;
    
    int main()
    {
        int n,a;
        scanf("%d",&n);
        set<int> Set;
        set<int>::iterator it;
        for(int i=0;i<n;i++)
        {
           scanf("%d",&a);
           if(Set.empty())
               Set.insert(a);
           else
           {
               it=Set.lower_bound(a);//理解为找到比a大的最小数
               if(it==Set.end())
                   Set.insert(a);
               else
               {   
                   Set.erase(it);  
                   Set.insert(a);  
               }
           }
        }
        printf("%d\n",Set.size());
        return 0;
    }

[lp_o9wf01q8p76.jpg]: /images/20220705/9dd211173782497ab1c3cfd15085e8e4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】STL 容器 - set 集合容器 ① ( set 集合容器简介 | set 集合容器操作的时间复杂度 | set 集合容器常用操作 )

文章目录一、set 集合容器 1、set 集合容器简介 2、set 集合容器操作的时间复杂度 3、set 集合容器常用操作

素颜马尾好姑娘i/ 2024年02月05日 19:27/ 0 赞/ 47 阅读

相关 set容器

set/multiset的简介 set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

素颜马尾好姑娘i/ 2023年07月17日 11:21/ 0 赞/ 59 阅读

相关 bilibiliC++57-64_STL常用容器_set/ multiset 容器

3.8 set/ multiset 容器 3.8.1 set基本概念简介：所有元素都会在插入时自动被排序本质： set/multiset属于

谁践踏了优雅/ 2022年10月30日 02:28/ 0 赞/ 227 阅读

相关巧用set容器

L2-014. 列车调度时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作

短命女/ 2022年09月30日 12:54/ 0 赞/ 207 阅读

相关巧用coalesce

现在有这么一个需求，小区有几个联系人，现在停电，先通知联系人1，如果没有则通知联系人2，否则还没有则通知联系人3. create table test( i

一时失言乱红尘/ 2022年08月06日 10:27/ 0 赞/ 212 阅读

相关巧用border

本文原创地址：[http://blog.csdn.net/zhou\_xiao\_cheng/article/details/54318682][http_blog.csdn.

谁践踏了优雅/ 2022年07月13日 13:20/ 0 赞/ 226 阅读

相关二进制巧用

求下面函数的返回值 ------统计x的二进制形式中1的个数 \------------------------------------- int func(int x

小咪咪/ 2022年06月17日 13:10/ 0 赞/ 211 阅读

相关 set 容器

//set 容器里面不可以有重复的元素 //a 和 b 重复 == “a必须排在b前面” 和 “b必须排在前面”都不成立 include<iostrea

迷南。/ 2022年06月16日 11:41/ 0 赞/ 213 阅读

相关巧用PopupWindow

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] PopupWindow是一种简便的弹出界面，常用的场合是

谁践踏了优雅/ 2022年01月16日 04:53/ 0 赞/ 298 阅读

相关 set容器

问题及代码： /copyright(c)2016.烟台大学计算机学院 All rights reserved, 文件名称：text.C

雨点打透心脏的1/2处/ 2021年06月10日 20:41/ 0 赞/ 506 阅读