前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【2020HBU天梯赛训练】7-40 列车调度

【2020HBU天梯赛训练】7-40 列车调度

作者头像
韩旭051
发布2020-06-23 11:49:07
4310
发布2020-06-23 11:49:07
举报
文章被收录于专栏:刷题笔记

7-40 列车调度

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

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

输入格式:

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

输出格式:

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

输入样例:

代码语言:javascript
复制
9
8 4 2 5 3 9 1 6 7

输出样例:

代码语言:javascript
复制
4

set奇解 set自动排序 直接定位

代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int num,n;
    cin>>n;
    set<int> s;
    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);
    }
    cout<<s.size();
    return 0;
}

用数组加sort超时,

代码语言:javascript
复制
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>num(n);
	for(int i=0;i<n;i++)cin>>num[i];
	vector<int>ans;
	ans.push_back(num[0]);
	for(int i=1;i<n;i++){
		int flag=1;
		sort(ans.begin(),ans.end());
		for(int j=0;j<ans.size();j++){
			if(ans[j]>=num[i]){
				//cout<<"&&"<<ans[j]<<"^^"<<num[i]<<"&&"<<endl;
				ans[j]=num[i];
				flag=0;	
				break;
			}
		}if(flag){
			ans.push_back(num[i]);
			//cout<<num[i]<<"****"<<endl;	
		}
	}cout<<ans.size();
	return 0;
} 

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/02/04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 7-40 列车调度
    • 输入格式:
      • 输出格式:
        • 输入样例:
          • 输出样例:
          • set奇解 set自动排序 直接定位
          • 用数组加sort超时,
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档