题目描述
现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
例如:
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入输出格式
输入格式:
输入一共有两行,第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式:
输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
8 3
1 3 -1 -3 5 3 6 7
-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 滑动窗口的更多相关文章
-
洛谷P1886 滑动窗口(POJ.2823 Sliding Window)(区间最值)
To 洛谷.1886 滑动窗口 To POJ.2823 Sliding Window 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每 ...
-
[POJ2823][洛谷P1886]滑动窗口 Sliding Window
题目大意:有一列数,和一个窗口,一次能框连续的s个数,初始时窗口在左端,不断往右移动,移到最右端为止,求每次被框住的s个数中的最小数和最大数. 解题思路:这道题是一道区间查询问题,可以用线段树做.每个 ...
-
洛谷 P1886 滑动窗口(单调队列)
题目链接 https://www.luogu.org/problemnew/show/P1886 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始 ...
-
洛谷P1886滑动窗口
题目传送门 理解题意:给定一个数列和窗口范围k,求依次向右移动窗口时每次窗口内的最大和最小值. 没什么思维难度,一边扫过去,用两个数组maxx和minn记录每个窗口内的最大最小值,移动过程中用两个变量 ...
-
[洛谷P1886]滑动窗口 (单调队列)(线段树)
---恢复内容开始--- 这是很好的一道题 题目描述: 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口. 现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的 ...
-
洛谷 P1886 滑动窗口 (数据与其他网站不同。。)
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
洛谷——P1886 滑动窗口|| POJ——T2823 Sliding Window
https://www.luogu.org/problem/show?pid=1886#sub || http://poj.org/problem?id=2823 题目描述 现在有一堆数字共N个数字( ...
-
洛谷 P1886 滑动窗口(单调队列)
嗯... 题目链接:https://www.luogu.org/problem/P1886 首先这道题很典型,是标准的单调队列的模板题(也有人说单调队列只能解决这一个问题).这道题可以手写一个队列,也 ...
-
洛谷 P1886 滑动窗口 /【模板】单调队列
纯板子题,入队时保证单调性,即单调栈,出队保证题目条件,本题即窗口长度k,在入队出队时都可以维护信息 ; int buf[maxm], maxq[maxm], minq[maxm], ans1[max ...
随机推荐
-
JS中的原型继承机制
转载 http://blog.csdn.net/niuyongjie/article/details/4810835 在学习JS的面向对象过程中,一直对constructor与prototype感到很 ...
-
div 显示滚动条的CSS代码
div 显示滚动条的CSS代码 div显示上下左右滚动条 <div style="width:260px;height:120px; overflow:scroll; border ...
-
.NET的 DataTable中某列求和
public DataTable ReportDetail { get; set; }//定义datatable属性 this.txtTotalPiece.Text = ReportDetail.Co ...
-
JAVA笔记(一)super and this
http://zhangjunhd.blog.51cto.com/113473/20531 总结关键字this与super用法. author: ZJ 07-3-12 Blog: [url]http: ...
-
Wcf 文件上传下载
wcf 文件上传的例子网上很多,我也是借鉴别人的示例.wcf 文件下载的示例网上就很少了,不知道是不是因为两者的处理方式比较类似,别人就没有再上传了.在此本人做下记录备忘. UploadFile.sv ...
-
efwplusUI框架,支持在Liunx服务器运行的Web开发框架,C#开发
efwplusUI开发框架 这是一个简单Web框架,前台采用amaze UI +requireJS+handlebarsJS,后台采用WebApi+MongoDB,用Nginx做Http服务器,随着. ...
-
php中获取中文首字母程序代码
年会抽奖,要求一等奖的中奖概率是0.12%,二等奖中奖概率是3%,三等奖中奖概率是12%,其他中奖概率是都是谢谢惠顾. <?php /** * 抽奖 * @param int $total */ ...
-
关于 construct object opp
constructor 定义和用法 constructor 属性返回对创建此对象的数组函数的引用. 语法 object.constructor 实例 例子 1 在本例中,我们将展示如何使用 const ...
-
(转)Content-Disposition的使用和注意事项
最近不少Web技术圈内的朋友在讨论协议方面的事情,有的说web开发者应该熟悉web相关的协议,有的则说不用很了解.个人认为这要分层次来看待这个问 题,对于一个新手或者刚入门的web开发人员而言,研究协 ...
-
关于开发环境无法运行applet
测试一下IE java vm 如果没有正确显示出来,说明java vm插件没有装好: 我用Uninstalle 来清理注册表:重装jdk 1.6_45