洛谷 P1886 滑动窗口

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

题目描述

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

例如:

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

洛谷 P1886 滑动窗口

输入输出格式

输入格式:

输入一共有两行,第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式:

输出共两行,第一行为每次窗口滑动的最小值

第二行为每次窗口滑动的最大值

输入输出样例

输入样例#1:
8 3
1 3 -1 -3 5 3 6 7
输出样例#1:
-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明

50%的数据,n<=10^5

100%的数据,n<=10^6

 #include<iostream>
#include<cstdio>
#include<cstring>
#define N 10000000
using namespace std;
int n,k,a[N],q[N],p[N];
void MIN()
{
int head=,tail=;
for(int i=;i<k;i++)
{
while(head<=tail&&q[tail]>=a[i])
tail--;
q[++tail]=a[i];
p[tail]=i;
}
for(int i=k;i<=n;i++)
{
while(head<=tail&&q[tail]>=a[i])
tail--;
q[++tail]=a[i];
p[tail]=i;
while(p[head]<=i-k)
head++;
printf("%d ",q[head]);
if(i==n) printf("\n");
}
}
void MAX()
{
int head=,tail=;
for(int i=;i<k;i++)
{
while(head<=tail&&q[tail]<=a[i])
tail--;
q[++tail]=a[i];
p[tail]=i;
}
for(int i=k;i<=n;i++)
{
while(head<=tail&&q[tail]<=a[i])
tail--;
q[++tail]=a[i];
p[tail]=i;
while(p[head]<=i-k)
head++;
printf("%d ",q[head]);
if(i==n) printf("\n");
}
}
int main()
{
cin>>n>>k;
for(int i=;i<=n;i++)
cin>>a[i];
MIN();
MAX(); return ;
}

思路:单调队列~~

洛谷 P1886 滑动窗口的更多相关文章

  1. 洛谷P1886 滑动窗口(POJ&period;2823 Sliding Window)(区间最值)

    To 洛谷.1886 滑动窗口 To POJ.2823 Sliding Window 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每 ...

  2. &lbrack;POJ2823&rsqb;&lbrack;洛谷P1886&rsqb;滑动窗口 Sliding Window

    题目大意:有一列数,和一个窗口,一次能框连续的s个数,初始时窗口在左端,不断往右移动,移到最右端为止,求每次被框住的s个数中的最小数和最大数. 解题思路:这道题是一道区间查询问题,可以用线段树做.每个 ...

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

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

  4. 洛谷P1886滑动窗口

    题目传送门 理解题意:给定一个数列和窗口范围k,求依次向右移动窗口时每次窗口内的最大和最小值. 没什么思维难度,一边扫过去,用两个数组maxx和minn记录每个窗口内的最大最小值,移动过程中用两个变量 ...

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

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

  6. 洛谷 P1886 滑动窗口 &lpar;数据与其他网站不同。。&rpar;

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

  7. 洛谷——P1886 滑动窗口&vert;&vert; POJ——T2823 Sliding Window

    https://www.luogu.org/problem/show?pid=1886#sub || http://poj.org/problem?id=2823 题目描述 现在有一堆数字共N个数字( ...

  8. 洛谷 P1886 滑动窗口(单调队列)

    嗯... 题目链接:https://www.luogu.org/problem/P1886 首先这道题很典型,是标准的单调队列的模板题(也有人说单调队列只能解决这一个问题).这道题可以手写一个队列,也 ...

  9. 洛谷 P1886 滑动窗口 &sol;【模板】单调队列

    纯板子题,入队时保证单调性,即单调栈,出队保证题目条件,本题即窗口长度k,在入队出队时都可以维护信息 ; int buf[maxm], maxq[maxm], minq[maxm], ans1[max ...

随机推荐

  1. JS中的原型继承机制

    转载 http://blog.csdn.net/niuyongjie/article/details/4810835 在学习JS的面向对象过程中,一直对constructor与prototype感到很 ...

  2. div 显示滚动条的CSS代码

    div 显示滚动条的CSS代码   div显示上下左右滚动条 <div style="width:260px;height:120px; overflow:scroll; border ...

  3. &period;NET的 DataTable中某列求和

    public DataTable ReportDetail { get; set; }//定义datatable属性 this.txtTotalPiece.Text = ReportDetail.Co ...

  4. JAVA笔记(一)super and this

    http://zhangjunhd.blog.51cto.com/113473/20531 总结关键字this与super用法. author: ZJ 07-3-12 Blog: [url]http: ...

  5. Wcf 文件上传下载

    wcf 文件上传的例子网上很多,我也是借鉴别人的示例.wcf 文件下载的示例网上就很少了,不知道是不是因为两者的处理方式比较类似,别人就没有再上传了.在此本人做下记录备忘. UploadFile.sv ...

  6. efwplusUI框架,支持在Liunx服务器运行的Web开发框架,C&num;开发

    efwplusUI开发框架 这是一个简单Web框架,前台采用amaze UI +requireJS+handlebarsJS,后台采用WebApi+MongoDB,用Nginx做Http服务器,随着. ...

  7. php中获取中文首字母程序代码

    年会抽奖,要求一等奖的中奖概率是0.12%,二等奖中奖概率是3%,三等奖中奖概率是12%,其他中奖概率是都是谢谢惠顾. <?php /** * 抽奖 * @param int $total */ ...

  8. 关于 construct object opp

    constructor 定义和用法 constructor 属性返回对创建此对象的数组函数的引用. 语法 object.constructor 实例 例子 1 在本例中,我们将展示如何使用 const ...

  9. &lpar;转&rpar;Content-Disposition的使用和注意事项

    最近不少Web技术圈内的朋友在讨论协议方面的事情,有的说web开发者应该熟悉web相关的协议,有的则说不用很了解.个人认为这要分层次来看待这个问 题,对于一个新手或者刚入门的web开发人员而言,研究协 ...

  10. 关于开发环境无法运行applet

    测试一下IE java vm 如果没有正确显示出来,说明java vm插件没有装好: 我用Uninstalle 来清理注册表:重装jdk 1.6_45