巧用set容器

短命女 2022-09-30 12:54 162阅读 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 条评论，162人围观）

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

相关阅读

相关 stl set容器_C ++ STL设置容器– std :: set

![6495602ae9fd2526e245115a23f7e51f.png][] stl set容器 In this tutorial you will learn ab

偏执的太偏执、/ 2022年12月07日 13:54/ 0 赞/ 198 阅读

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

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

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

相关巧用set容器

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

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

相关巧用coalesce

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

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

相关巧用border

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

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

相关二进制巧用

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

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

相关 set 容器

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

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

相关巧用PopupWindow

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

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

相关巧用set集合的intersection（交集）和difference（差集）

intersection: 描述： intersection()方法用于返回两个或更多集合中都包含的元素，即交集。语法： set.intersection

悠悠/ 2021年11月02日 10:46/ 0 赞/ 261 阅读

相关 set容器

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

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