文档章节

双端队列

o
 osc_fmg49rzg
发布于 2019/03/20 13:40
字数 412
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

问题 F: 双端队列

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 11
[提交] [状态] [命题人:admin]

题目描述

Sherry现在碰到了一个棘手的问题,有N个整数需要排序。
Sherry手头能用的工具就是若干个双端队列。   
她需要依次处理这N个数,对于每个数,Sherry能做以下两件事:
1.新建一个双端队列,并将当前数作为这个队列中的唯一的数;
2.将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后,Sherry将这些队列排序后就可以得到一个非降的序列。

 

输入

第一行包含一个整数N(N≤200000),表示整数的个数。接下来的N行每行包含一个整数Di,其中Di表示所需处理的整数。

 

输出

其中只包含一行,为Sherry最少需要的双端队列数。

 

样例输入

复制样例数据

6
3
6
0
9
6
3

样例输出

2
#include <bits/stdc++.h>

using namespace std;
const int maxn=2e5+5;
pair<int,int>p[maxn];
pair<int,int>q[maxn];
int n,increase=1,cnt,pre=0x3f3f3f3f,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i].first;
        q[i].second=i;
    }
    sort(q+1,q+1+n);
    for(int i=1;i<=n;i++){
        if(i==1||q[i].first!=q[i-1].first){
            p[cnt].second=q[i-1].second;
            p[++cnt].first=q[i].second;
        }
    }
    p[cnt].second=q[n].second;
    for(int i=1;i<=cnt;i++){
        if(increase){
            if(pre<p[i].first)pre=p[i].second;
            else pre=p[i].first,ans++,increase=0;
        }
        else{
            if(pre>p[i].second)pre=p[i].first;
            else pre=p[i].second,increase=1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Java的Queue集合

Queue用于模拟队列这种数据结构,队列通常是指“先进先出”FIFO的容器,队列的头部保存在队列中存放时间最长的元素,队列的尾部保存在队列中存放时间最短的元素。Queue接口中定义了如下几个方...

西红柿的眼泪
2016/07/14
56
0
python算法与数据结构-队列(44)

一、队列的介绍   队列的定义:队列是一种特殊的线性表,只允许在表的头部(front处)进行删除操作,在表的尾部(rear处)进行插入操作的线性数据结构,这种结构就叫做队列。进行插入操作的...

osc_d4gurmqk
2019/07/04
5
0
自己动手实现java数据结构(四)双端队列

1.双端队列介绍   在介绍双端队列之前,我们需要先介绍队列的概念。和栈相对应,在许多算法设计中,需要一种"先进先出(First Input First Output)"的数据结构,因而一种被称为"队列(Queue)...

小熊餐馆
2018/12/19
0
0
自己动手实现java数据结构(四)双端队列

1.双端队列介绍   在介绍双端队列之前,我们需要先介绍队列的概念。和栈相对应,在许多算法设计中,需要一种"先进先出(First Input First Output)"的数据结构,因而一种被称为"队列(Queue)...

osc_b07navmi
2018/12/19
1
0
Java.util.ArrayDeque类

介绍 所述java.util.ArrayDeque中类提供可调整大小的阵列,并实现的Deque接口。以下是Array Deques的重点 数组deques没有容量限制,因此它们会根据需要增长以支持使用。 它们不是线程安全的;...

果果糖
2019/03/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

敖丙20 张图揭开内存管理的迷雾

前言 之前有不少读者跟我反馈,能不能写图解操作系统? 既然那么多读者想看,我最近就在疯狂的复习操作系统的知识。 操作系统确实是比较难啃的一门课,至少我认为比计算机网络难太多了,但它...

敖丙
07/02
11
0
拉勾网拉你上勾

预览 需求简介 拉勾网是一个互联网行业的一个招聘网站,上面有许多职位,于是乎,小编想提取指定职位的基本信息(职位名,薪水,工作经验,工作地点,教育背景),然后插入 MongoDB 数据库,...

木下瞳
2019/04/17
20
0
我是一个线程(第一人称)

来源 | 转自 码农翻身 作者 | 刘欣 全文总共 | 4600 字 预计阅读时间 | 12 分钟 第一回 初生牛犊 我是一个线程,我一出生就被编了个号:0x3704,然后被领到一个昏暗的屋子里,在这里我发现了...

geniusian
2019/11/04
16
0
SkyWalking 权限认证

版本:7.0.0 描述 为了数据传输安全,确保网络连接是安全的。采用 Token 认证确保采集的应用数据是被信任的。 当前版本,仅支持简单的字符串 Token 配置 代理端配置文件agent.config设置 # ...

zm123321
41分钟前
17
0
是否允许实体正文进行HTTP DELETE请求? - Is an entity body allowed for an HTTP DELETE request?

问题: When issuing an HTTP DELETE request, the request URI should completely identify the resource to delete. 发出HTTP DELETE请求时,请求URI应该完全标识要删除的资源。 However,......

javail
昨天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部