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 条评论
登录 后参与评论

相关文章

来自专栏Hongten

SQL SERVER事务处理

事务三种运行模式: 自动提交事务 每条单独的语句都是一个事务。 显式事务 每个事务均以 BEGIN TRANSACTION 语句显式开始, 以 COMMIT 或...

782
来自专栏java架构师

SQL 写入调优

今天看到一篇非常适合本人这种数据库调优小白级别的人学的文章,做个笔记,学习之。 首先建一个用户表: CREATE TABLE [dbo].[jk_users](...

2536
来自专栏Java Edge

掌握 @transactional 注解@Transactional 注解管理事务的实现步骤Spring 的注解方式的事务实现机制

2766
来自专栏沃趣科技

会话和锁信息查询视图 | 全方位认识 sys 系统库

在上一篇《等待事件统计视图 | 全方位认识 sys 系统库》中,我们介绍了sys 系统库中的等待事件统计视图,本期的内容先给大家介绍会话信息和锁等待信息查询视图...

840
来自专栏微服务生态

从0到1起步-跟我进入堆外内存的奇妙世界

堆外内存一直是Java业务开发人员难以企及的隐藏领域,究竟他是干什么的,以及如何更好的使用呢?那就请跟着我进入这个世界吧。

682
来自专栏乐沙弥的世界

MyCAT全局表描述及示例

791
来自专栏Spark学习技巧

Spark调优系列之序列化方式调优

由于大多数的spark计算是基于内存的的天性,spark应用的瓶颈一般受制于集群的CPU,网络带宽,内存。大部分情况下,如果内存适合当前数据量的计算,那么瓶颈往...

2579
来自专栏存储技术

MySQL加锁范围分析

最近,遇到了一个关于mysql 加锁的问题,将当时的情形简化如下,有一个index_test表,表结构如下所示:

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

【源码剖析】- Spark 新旧内存管理方案(下)

上一篇文章【源码剖析】- Spark 新旧内存管理方案(上)介绍了旧的内存管理方案以及其实现类 StaticMemoryManager 是如何工作的,本文将通过...

542
来自专栏技术碎碎念

OS存储器管理(二)

离散分配 分页(Paging),分段,段页式 一、分页 一个进程的物理地址可以是非连续的; 将物理内存分成固定大小的块,称为块(frame); 将逻辑内存分为同...

3198

扫码关注云+社区