[Luogu P1886]滑动窗口--单调队列入门

时间:2022-01-29 22:31:35

题目描述

现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

例如:

The array is [1 3 -1 -3 5 3 6 7], and k = 3.

[Luogu P1886]滑动窗口--单调队列入门

输入输出格式

输入格式:

输入一共有两行,第一行为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]滑动窗口--单调队列入门的更多相关文章

  1. 洛谷 P1886 滑动窗口&lpar;单调队列&rpar;

    题目链接 https://www.luogu.org/problemnew/show/P1886 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始 ...

  2. &lbrack;洛谷P1886&rsqb;滑动窗口 &lpar;单调队列&rpar;&lpar;线段树&rpar;

    ---恢复内容开始--- 这是很好的一道题 题目描述: 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口. 现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的 ...

  3. P1886 滑动窗口 单调队列

    题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...

  4. Luogu P1886 滑动窗口

    P1886 滑动窗口 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The a ...

  5. luogu P1886 滑动窗口(单调队列

    题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...

  6. 【洛谷P1886】滑动窗口——单调队列

    没想到啊没想到,时隔两个月,我单调队列又懵了…… 调了一个小时,最后错在快读,啊!!!!(不过洛谷讨论真好啊,感谢大佬!) 考前就不推新东西了,好好写写那些学过的东西 题目点这里(我就不粘了自己点一下 ...

  7. cogs 495&period; 滑动窗口 单调队列

    495. 滑动窗口 ★★   输入文件:window.in   输出文件:window.out   简单对比时间限制:2 s   内存限制:256 MB [问题描述] 给你一个长度为N的数组,一个长为 ...

  8. luoguP1886 滑动窗口 &lbrack;单调队列&rsqb;

    题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...

  9. &lbrack;POJ2823&rsqb;Sliding Window 滑动窗口&lpar;单调队列&rpar;

    题意 刚学单调队列的时候做过 现在重新做一次 一个很经典的题目 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗 ...

随机推荐

  1. redis学习教程之一基本命令

    参阅redis中文的 互动教程(interactive tutorial)来学习的. 目录: 全局操作 get  get incr  自增 del 删除 expire 定时 list  队列 set ...

  2. Linux进程间通信:IPC对象——信号灯集详解

    作者:倪老师,华清远见嵌入式学院讲师. 一.信号灯概述 信号灯与其他进程间通信方式不大相同,它主要提供对进程间共享资源访问控制机制.相当于内存中的标志,进程可以根据它判定是否能够访问某些共享资源,同时 ...

  3. android 手风琴

    引用:http://note.youdao.com/share/?id=994df799c2dcc8d83a8909173e42f80d&type=note 先看效果,过瘾一番. 源码下载:h ...

  4. PHP批量过滤MYSQL数据库内站外链接和图片

    因发现站内很多引用站外文章的链接失效,产生大量的死链接,对于搜索引擎来说是极不友好的,很不利于网站优化,所以站内添加了站外链接过滤功能,对于新加的文章,在添加入库时就自动增加rel="nof ...

  5. 蝇量模式(Flyweight Pattern)

    蝇量模式:让某个类的一个实例能用来提供许多“虚拟实例”. 在有大量对象时,有可能造成内存溢出,把其*同的部分抽象出来,如果有相同的业务请求,直接返回在内存中已有的对象,避免重复创建.(JAVA中的S ...

  6. Detect combined string

    写一个程序判断字符串A是否为其他两个字符串的组合,组合过程中其他两个字符串的相对顺序不能被破坏. 举例说明:abc和def可以组成字符串adebcf,但不能组成aefbcd,因为def的相对顺序已经被 ...

  7. Single Number 解答

    Question Given an array of integers, every element appears twice except for one. Find that single on ...

  8. Nginx 模块开发(1)—— 一个稍稍能说明问题模块开发 Step By Step 过程

    1. Nginx 介绍        Nginx是俄罗斯人编写的十分轻量级的HTTP服务器,它的发音为“engine X”, 是一个高性能的HTTP和反向代理服务器,同时也是一个IMAP/POP3/S ...

  9. unix命令&colon; ifconfig

    ifconfig 命令被用来: 1.为一个网卡分配一个IP地址 2.设置本地环路界面 3.分配一个子网掩码(可选) HP-UX: # /usr/sbin/ifconfig lan0 lan0: fla ...

  10. hdu4521 小明系列的问题——小明序列&lpar;LIS变种 (段树&plus;单点更新解决方案)&rpar;

    链接: huangjing 题目:中文题目 思路: 1:这个题目假设去掉那个距离大于d的条件,那么必定是一个普通的LIS.可是加上那个条件后就变得复杂了.我用的线段树的解法. . .就是採用延迟更新的 ...