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.
输入输出格式
输入格式:
输入一共有两行,第一行为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
代码:
洛谷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)(区间最值)的更多相关文章
-
洛谷——P1886 滑动窗口|| POJ——T2823 Sliding Window
https://www.luogu.org/problem/show?pid=1886#sub || http://poj.org/problem?id=2823 题目描述 现在有一堆数字共N个数字( ...
-
[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的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
[洛谷P1886]滑动窗口 (单调队列)(线段树)
---恢复内容开始--- 这是很好的一道题 题目描述: 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口. 现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的 ...
-
洛谷 P1886 滑动窗口 (数据与其他网站不同。。)
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
洛谷 P1886 滑动窗口(单调队列)
嗯... 题目链接:https://www.luogu.org/problem/P1886 首先这道题很典型,是标准的单调队列的模板题(也有人说单调队列只能解决这一个问题).这道题可以手写一个队列,也 ...
-
洛谷 P1886 滑动窗口 /【模板】单调队列
纯板子题,入队时保证单调性,即单调栈,出队保证题目条件,本题即窗口长度k,在入队出队时都可以维护信息 ; int buf[maxm], maxq[maxm], minq[maxm], ans1[max ...
随机推荐
-
利用jquery获取html中被选中的input的值
单个按钮 <div id="wrap"> <input type="radio" name="payMethod" val ...
-
SRV记录说明
SRV记录是DNS服务器的数据库中支持的一种资源记录的类型,它记录了哪台计算机提供了哪个服务这么一个简单的信息 SRV 记录:一般是为Microsoft的活动目录设置时的应用.DNS可以独立于活动 ...
-
这么小的key-val数据库居然也支持事务——与短跑名将同名的数据库Bolt
传送门: 柏链项目学院 什么是Bolt? Bolt是一个纯净的基于go语言编写的key-val数据库,该项目受到LMDB项目的启发,目标是提供一个不需要完整服务器的简单.快速.可靠的数据库. ...
-
【转】TCP和SOCKET关系
socket是TCP/IP协议的API TCP是数据的介质,Socket是TCP的介质. 查了一下RFC文档,Socket是RFC147,更新时间是1971年.TCP是RFC793,更新时间是19 ...
-
拦截$.ajax方法实现登录过期登录
jQuery(function ($) { var CreateLoginWindows = function (callback) { var h = 300; $('#CreateLoginWin ...
-
ViewResolver和JSTL
---------------------siwuxie095 ViewResolver 和 JSTL 1.Spring ...
-
20172319 实验四 《Android程序设计》实验报告
20172319 2018.05.17-30 实验四<Android程序设计> 实验报告 课程名称:<程序设计与数据结构> 学生班级:1723班 学生姓名:唐才铭 学生学号:2 ...
-
【剑指offer】栈的压入、弹出序列
一.题目: 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序.假设压入栈的所有数字均不相等.例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该 ...
-
DB磁盘满导致Zabbix Server Crash一例
故障描述 今天线上zabbix出现几次数据中断的情况,经排查为DB服务器磁盘空间不足导致的.还好我们目前我们zabbix,falcon两套监控系统并存,哈哈. 故障排查过程没什么技术含量,简单的将故障 ...
-
通过日志查看Web Api详细运行过程
1. 通过Nuget安装System.Web.Http.Tracing. 2. 通过HttpConfiguration,注册SystemDiagnosticsTraceWriter public st ...