题目描述
现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
例如:
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入输出格式
输入格式:
输入一共有两行,第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式:
输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
这题是单调队列入门题。题意清晰明了,求区间最大(小)。第一反应是线段树或者RMQ,但是数据范围爆炸。这道题和普通的区间的区别就在于它的区间长度是固定的。所以使用时间复杂度为O(n)的单调队列来解决。
什么是单调队列呢?单调队列是一种特殊的双端队列,其内部具有单调性(有点像优先序列,但有着本质区别)。
如何实现插入?从队尾插入,若破坏了单调性,则删除队尾元素(这个删除决定了什么题能用什么题不能用),直到找到一个不影响的位置。
如何实现输出?访问队首(真是方便)
如何解决这道题?首先设一个区间为(l,r),则有max(l+1,r+1)=max(a[r+1],max(a[l+1],a[l+2]...a[r])),那么max(l+1,r+1)与max(l,r)其实是有很大一部分重叠的,那么在问题实现的时候就只需要先删除单调队列中不在区间里的数(a[l]),再插入新数(a[r+1]),剩余的不变,就可以解决了。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
int res=,f=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
res=res*+(ch-'');
ch=getchar();
}
return res*f;
}
const int N=1e6+;
int nsf[N],nbf[N],que[N],number[N],a[N];
int n,k,head,tail;
inline void INT(){
n=read();k=read();
for(int i=;i<=n;++i)a[i]=read();
}
inline void findmin(){
head=;tail=;//队头、尾初始化
for(int i=;i<=n;++i){//插入a[i]到单调序列
while(number[head]<i-k+&&head<=tail)++head;
//从队首开始找,“过时”的删除
while(a[i]<=que[tail]&&head<=tail)--tail;
//插入时从队尾插入,维护单调上升性质
number[++tail]=i;que[tail]=a[i];
//number保存插入时的“时间戳”,que表示值
nsf[i]=que[head];//当前队列中最小值
}
}
inline void findmax(){
head=;tail=;
for(int i=;i<=n;++i){
while(number[head]<i-k+&&head<=tail)++head;
while(a[i]>=que[tail]&&head<=tail)--tail;
number[++tail]=i;que[tail]=a[i];
nbf[i]=que[head];
}
}
int main(){
INT();//输入
findmin();//动态规划求单调队列最小值
findmax();
for(int i=k;i<=n;++i)printf("%d ",nsf[i]);
cout<<endl;
for(int i=k;i<=n;++i)printf("%d ",nbf[i]);
return ;
}
第一次写随笔还有点小兴奋呢~
[Luogu P1886]滑动窗口--单调队列入门的更多相关文章
-
洛谷 P1886 滑动窗口(单调队列)
题目链接 https://www.luogu.org/problemnew/show/P1886 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始 ...
-
[洛谷P1886]滑动窗口 (单调队列)(线段树)
---恢复内容开始--- 这是很好的一道题 题目描述: 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口. 现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的 ...
-
P1886 滑动窗口 单调队列
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
Luogu P1886 滑动窗口
P1886 滑动窗口 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The a ...
-
luogu P1886 滑动窗口(单调队列
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
【洛谷P1886】滑动窗口——单调队列
没想到啊没想到,时隔两个月,我单调队列又懵了…… 调了一个小时,最后错在快读,啊!!!!(不过洛谷讨论真好啊,感谢大佬!) 考前就不推新东西了,好好写写那些学过的东西 题目点这里(我就不粘了自己点一下 ...
-
cogs 495. 滑动窗口 单调队列
495. 滑动窗口 ★★ 输入文件:window.in 输出文件:window.out 简单对比时间限制:2 s 内存限制:256 MB [问题描述] 给你一个长度为N的数组,一个长为 ...
-
luoguP1886 滑动窗口 [单调队列]
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
[POJ2823]Sliding Window 滑动窗口(单调队列)
题意 刚学单调队列的时候做过 现在重新做一次 一个很经典的题目 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗 ...
随机推荐
-
redis学习教程之一基本命令
参阅redis中文的 互动教程(interactive tutorial)来学习的. 目录: 全局操作 get get incr 自增 del 删除 expire 定时 list 队列 set ...
-
Linux进程间通信:IPC对象——信号灯集详解
作者:倪老师,华清远见嵌入式学院讲师. 一.信号灯概述 信号灯与其他进程间通信方式不大相同,它主要提供对进程间共享资源访问控制机制.相当于内存中的标志,进程可以根据它判定是否能够访问某些共享资源,同时 ...
-
android 手风琴
引用:http://note.youdao.com/share/?id=994df799c2dcc8d83a8909173e42f80d&type=note 先看效果,过瘾一番. 源码下载:h ...
-
PHP批量过滤MYSQL数据库内站外链接和图片
因发现站内很多引用站外文章的链接失效,产生大量的死链接,对于搜索引擎来说是极不友好的,很不利于网站优化,所以站内添加了站外链接过滤功能,对于新加的文章,在添加入库时就自动增加rel="nof ...
-
蝇量模式(Flyweight Pattern)
蝇量模式:让某个类的一个实例能用来提供许多“虚拟实例”. 在有大量对象时,有可能造成内存溢出,把其*同的部分抽象出来,如果有相同的业务请求,直接返回在内存中已有的对象,避免重复创建.(JAVA中的S ...
-
Detect combined string
写一个程序判断字符串A是否为其他两个字符串的组合,组合过程中其他两个字符串的相对顺序不能被破坏. 举例说明:abc和def可以组成字符串adebcf,但不能组成aefbcd,因为def的相对顺序已经被 ...
-
Single Number 解答
Question Given an array of integers, every element appears twice except for one. Find that single on ...
-
Nginx 模块开发(1)—— 一个稍稍能说明问题模块开发 Step By Step 过程
1. Nginx 介绍 Nginx是俄罗斯人编写的十分轻量级的HTTP服务器,它的发音为“engine X”, 是一个高性能的HTTP和反向代理服务器,同时也是一个IMAP/POP3/S ...
-
unix命令: ifconfig
ifconfig 命令被用来: 1.为一个网卡分配一个IP地址 2.设置本地环路界面 3.分配一个子网掩码(可选) HP-UX: # /usr/sbin/ifconfig lan0 lan0: fla ...
-
hdu4521 小明系列的问题——小明序列(LIS变种 (段树+单点更新解决方案))
链接: huangjing 题目:中文题目 思路: 1:这个题目假设去掉那个距离大于d的条件,那么必定是一个普通的LIS.可是加上那个条件后就变得复杂了.我用的线段树的解法. . .就是採用延迟更新的 ...