PTA 7-2 列车调度(25 分)

7-2 列车调度(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
#include <iostream>  // 类比最长上升子序列做
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int dp[maxn],a;
int main()
{
    int n;
    scanf("%d",&n);
    int len=0;
    while(n--)
    {
        scanf("%d",&a);
        if(len==0||dp[len-1]<=a) dp[len++]=a;
        else
        {
            int pos = upper_bound(dp,dp+len,a) - dp;
            dp[pos] = min(dp[pos],a);
        }
    }
    printf("%d\n",len);
 return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Manacher算法 O(n)求最长回文串

最长回文 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

1805
来自专栏机器人网

ABB机器人编程方式

1、指令表IL   指令表(IL)由一系列指令组成。每条指令都由一个新行开始,包含一个操作符以及和操作符类型相关的一个或多个操作数,并用逗号分开。在指令前可以有...

2736
来自专栏magicsoar

全错位排列

全错位排列是由著名数学家欧拉提出的。 最典型的问题是装错信封问题 一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多...

17710
来自专栏海天一树

Codeforces Round #463 C.Permutation Cycle

一、题目 http://codeforces.com/contest/932/problem/C 二、分析 (一)何谓Permutation Cycle 以例1...

31510
来自专栏PingCAP的专栏

SuRF: 一个优化的 Fast Succinct Tries

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

1985
来自专栏aCloudDeveloper

算法导论第十一章 散列表

一、散列表的概念 本章介绍了散列表(or hash table)的概念、散列函数的设计及哈希冲突的处理。散列表(为了形象描述,我们通常叫槽)从表意上看是一种数...

1926
来自专栏python爬虫实战之路

使用bloomfilter修改scrapy-redis去重

这篇文章憋的太久了,断断续续战线拉了好长。这个也是属于喜马拉雅那个项目的一部分,还要再忙一阵子。请大家见谅。

632
来自专栏mukekeheart的iOS之旅

No.011 Container With Most Water

11. Container With Most Water Total Accepted: 86363 Total Submissions: 244589 Di...

2179
来自专栏牛肉圆粉不加葱

[Spark源码剖析] DAGScheduler提交stage

DAGScheduler通过调用submitStage来提交stage,实现如下:

592
来自专栏mukekeheart的iOS之旅

No.009 Palindrome Number

9. Palindrome Number Total Accepted: 136330 Total Submissions: 418995 Difficulty...

2167

扫码关注云+社区