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

时间:2021-08-23 21:49:29

To 洛谷.1886 滑动窗口 To POJ.2823 Sliding Window

题目描述

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

例如:

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

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

输入输出格式

输入格式:

输入一共有两行,第一行为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

代码:

洛谷70分TLE的线段树

 #include<cstdio>
#include<algorithm>
using namespace std;
const int N=; int n,k,From,To,Min[N<<],Max[N<<]; void read(int &now)
{
now=;int f=;char c=getchar();
while(c<''||c>'')
{
if(c=='-')f=-;
c=getchar();
}
while(c>=''&&c<='')now=now*+c-'',c=getchar();
now*=f;
} inline void PushUp(int rt)
{
Min[rt]=min(Min[rt<<],Min[rt<<|]);
Max[rt]=max(Max[rt<<],Max[rt<<|]);
} void Build(int l,int r,int rt)
{
if(l==r)
{
int t;
read(t);
Min[rt]=Max[rt]=t;
return;
}
int m=(l+r)>>;
Build(l,m,rt<<);
Build(m+,r,rt<<|);
PushUp(rt);
} int QueryMax(int l,int r,int rt,int L,int R)
{
if(L<=l && r<=R) return Max[rt];
int m=(l+r)>>,res=(<<);
if(L<=m) res=max(res,QueryMax(l,m,rt<<,L,R));
if(m<R) res=max(res,QueryMax(m+,r,rt<<|,L,R));
return res;
} int QueryMin(int l,int r,int rt,int L,int R)
{
if(L<=l && r<=R) return Min[rt];
int m=(l+r)>>,res=(<<);
if(L<=m) res=min(res,QueryMin(l,m,rt<<,L,R));
if(m<R) res=min(res,QueryMin(m+,r,rt<<|,L,R));
return res;
} int main()
{
read(n);read(k);
Build(,n,);
//From=1;To=k;
for(register int i=;i<=n-k+;i++)//,From++,To++
printf("%d ",QueryMin(,n,,i,i+k-));
printf("\n");
//From=1;To=k;
for(register int i=;i<=n-k+;i++)//,From++,To++
printf("%d ",QueryMax(,n,,i,i+k-));
return ;
}

TLE

常数优化十分可观的zkw线段树(然而我不会用)

 #include<cstdio>
#include<algorithm>
using namespace std;
const int N=; int n,k,M,Tree[N<<]; void read(int &now)
{
now=;int f=;char c=getchar();
while(c>''||c<'')
{
if(c=='-')f=-;
c=getchar();
}
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
now*=f;
} void BuildMin(int n)
{
for(int i=M-;i;--i)
Tree[i]=min(Tree[i<<],Tree[i<<|]);
} void BuildMax(int n)
{
for(int i=M-;i;--i)
Tree[i]=max(Tree[i<<],Tree[i<<|]);
} int QueryMin(int s,int t,int res)
{
for(s+=M,t+=M;s^t^;s>>=,t>>=)
{
if(~s&) res=min(res,Tree[s^]);
if(t&) res=min(res,Tree[t^]);
}
return res;
} int QueryMax(int s,int t,int res)
{
for(s+=M,t+=M;s^t^;s>>=,t>>=)
{
if(~s&) res=max(res,Tree[s^]);
if(t&) res=max(res,Tree[t^]);
}
return res;
} int main()
{
read(n);read(k);
for(M=;M<=n+;M<<=);
for(int i=M+;i<=M+n;i++)
read(Tree[i]);
BuildMin(n);
for(int i=;i<=n-k;++i)
printf("%d ",QueryMin(i,i+k+,1e9));
printf("\n");
BuildMax(n);
for(int i=;i<=n-k;++i)
printf("%d ",QueryMax(i,i+k+,-1e9));
return ;
}

AC

洛谷P1886 滑动窗口(POJ.2823 Sliding Window)(区间最值)的更多相关文章

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

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

  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. 洛谷 P1886 滑动窗口

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

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

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

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

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

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

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

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

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

随机推荐

  1. 利用jquery获取html中被选中的input的值

    单个按钮 <div id="wrap"> <input type="radio" name="payMethod" val ...

  2. SRV记录说明

      SRV记录是DNS服务器的数据库中支持的一种资源记录的类型,它记录了哪台计算机提供了哪个服务这么一个简单的信息 SRV 记录:一般是为Microsoft的活动目录设置时的应用.DNS可以独立于活动 ...

  3. 这么小的key-val数据库居然也支持事务——与短跑名将同名的数据库Bolt

    传送门: 柏链项目学院 什么是Bolt?   Bolt是一个纯净的基于go语言编写的key-val数据库,该项目受到LMDB项目的启发,目标是提供一个不需要完整服务器的简单.快速.可靠的数据库.    ...

  4. 【转】TCP和SOCKET关系

    socket是TCP/IP协议的API   TCP是数据的介质,Socket是TCP的介质. 查了一下RFC文档,Socket是RFC147,更新时间是1971年.TCP是RFC793,更新时间是19 ...

  5. 拦截&dollar;&period;ajax方法实现登录过期登录

    jQuery(function ($) { var CreateLoginWindows = function (callback) { var h = 300; $('#CreateLoginWin ...

  6. ViewResolver和JSTL

    ---------------------siwuxie095                                 ViewResolver 和 JSTL         1.Spring ...

  7. 20172319 实验四 《Android程序设计》实验报告

    20172319 2018.05.17-30 实验四<Android程序设计> 实验报告 课程名称:<程序设计与数据结构> 学生班级:1723班 学生姓名:唐才铭 学生学号:2 ...

  8. 【剑指offer】栈的压入、弹出序列

    一.题目: 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序.假设压入栈的所有数字均不相等.例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该 ...

  9. DB磁盘满导致Zabbix Server Crash一例

    故障描述 今天线上zabbix出现几次数据中断的情况,经排查为DB服务器磁盘空间不足导致的.还好我们目前我们zabbix,falcon两套监控系统并存,哈哈. 故障排查过程没什么技术含量,简单的将故障 ...

  10. 通过日志查看Web Api详细运行过程

    1. 通过Nuget安装System.Web.Http.Tracing. 2. 通过HttpConfiguration,注册SystemDiagnosticsTraceWriter public st ...