P1886 滑动窗口 /【模板】单调队列 题解

CSDN同步

原题链接

简要题意:

给定一个数组,求所有连续 (m) 个数的最大值和最小值。

首先,对于这种题目,用 (5+) 种方法(至少),这里介绍几种吧。

算法一

根据 ( exttt{RMQ}) 算法解决问题。

(f_{i,j}) 表示从 (i) 开始往后 (2^j) 个的最大值。((2^j > n) 则视为 (n)

那么,显然有:

[ f_{i,j} = egin{cases} a_i , j=0 \ f_{f_{i,j-1},j-1} , j ot = 0 \ end{cases} ]

其中,(f_{i,j-1}) 即往后先走 (2^{j-1}) 个, 再走 (2^{j-1}) 个,类似于 倍增 算法。

然后,预处理 (log),即可 (O(n log n)) 初始化,(O(1)) 回答。

时间复杂度:(O(n log n + k)).

期望得分:(50pts) ~ (100pts).(取决于程序常数,听说这道题目 卡任何带 (log) 的算法,不知道能不能卡过去)

算法二

分块,本题效率最慢的算法。

请不要轻看它,不信? 还有这个贴

显然,分成 (sqrt{n}) 块,对每块分别计算,对于 (n-k+1) 个块分别询问。

时间复杂度:(O((n-k+1) sqrt{n})), 如果是极限数据 (n=10^6)(k=1) 就直接卡掉了。((k) 很小就可以)

期望得分:(50pts) ~ (100pts).

实际得分:(92pts).(有人实测过,卡常得高分)

算法三

线段树,在分块与 ( ext{RMQ}) 之间。

这题的算法上有线段树但是过不了。。。

不用说了吧,模板在此.

时间复杂度:(O(n log n + k log n)). (显然被卡超时,不过:)

期望得分:(50pts) ~ (100pts).

实际得分:(92pts).(真·卡常大法好)

算法四

指令集。???

洛谷日报——指令集

学习完之后,相信你能随便用一个数据结构(甚至是暴力???)切掉本题!

时间复杂度:(O(n^2)) ~ (O(n log n + k log n)) ~ (O(n log n + k)).

期望得分:(100pts).

实际得分:(92pts) ~ (100pts).(众所周知数据加强过一次,要是加强之前交没准就过了,不然没准被卡)

算法五

扯了这么多。。终于到正题了!

单调队列 为什么叫这么名字,它不是白叫的好吧 像平衡树要是不平衡那要它干么呢

假设,现在一个君王他叫做 (CCF)(CCF = ext{Centre Code Forces})),有 (8) 名选手,她们(对,就是她)的才华值分别为:

1 3 -1 -3 5 3 6 7

她们从左往右依次是:zhk,yy,kkk,bfw,gyx,cz,wxq,rxz.

然后,他们参加 (CCF) 比赛的年龄分别为 (8) ~ (1) 岁。(嗯?没错)

(CCF) 有一个 怪癖:只要一个选手参加 (CCF) 比赛超过 (3) 年,她(?)就觉得该选手没有潜力了。

  • zhk(8) 岁的时候进入了,他发现没有一个人比他更厉害,所以他留下来了。

  • yy(7) 岁的时候也进入了 (CCF) 比赛,并把 zhk 踢下去,因为 (3>1). zhk 想:他比我小还比我强,我退役吧,然后就退役了。

  • kkk(6) 岁时一来,发现被 yy 吊打了((3 > -1)),但是他想:你比我强,但是我比你小,我更有潜力,我活的比你久,没准等你退役我就是老大! 于是留了下来。然后,( ext{CCF Round 1}) 冠军产生:yy.

  • bfw 一看:嗯?怎么前面的人都比我强啊?事实 然后他觉得,自己留下来的时间更久,等她们都退役再说。 于是留了下来。( ext{CCF Round 2}) 冠军产生:yy.

  • gyx 来了之后,他发现自己是最强的 (5>3),然后所有的人(除了她)都觉得 有人比我小还比我强,集体退役。yy 又遭到 (CCF) 的潜力质疑,精神病发作了。( ext{CCF Round 3}) 冠军产生:gyx.

  • cz 来了之后,嗯发现自己是最弱的,但是她想: CCF质疑 gyx 比我前,所以我比她活得长!活得长就是报仇,所以要留下来!( ext{CCF Round 4}) 冠军产生:gyx.

  • wxq 一到,瞬间 吊打集训队吊打全场然后 gyxcz 一起退役了。( ext{CCF Round 5}) 冠军产生:wxq.

  • 最后 rxz 到了,结束了 wxq(CCF) 生涯,把她弄自闭然后滚出集训队了。(我才不会告诉你 rxz 就是 (CCF) 出题人( ext{CCF Round 6}) 冠军产生:rxz.

若干年过去了,( ext{CCF}) 决定:分数越低的人得奖越高,那些强者实在弱不下来,于是又开始了第二场 互逼退役 的旅程。。

综上可见,单调队列的过程本质就是一个维护队列的过程,参加 (CCF) 则入队,退役则出队。

显然,如果用系统的 ( ext{queue}) 写会多出一个 (log),然后变成 (O(n log n)) 级别,沦为和上述数据结构一样的。(智商不够,数据结构来凑

所以今天我们用 手写队列,用 (l,r) 指针维护当前在队列中的元素。

时间复杂度:(O(n + k )).

实际得分:(100pts).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,m,a[N];
int q[N],p[N]; //q[i] 记录数值 , p[i] 记录编号

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
//	for(int i=1;i<=n;i++) printf("%d ",a[i]); puts("");
	int l=1,r=0;
	for(int i=1;i<=n;i++) {
		while(l<=r && q[r]>=a[i]) r--; //新来的人先吊打掉一波
		q[++r]=a[i]; p[r]=i;
		while(p[l]<=i-m) l++; //被质疑的可以直接退役
//		printf("%d %d
",l,r);
		if(i>=m) printf("%d ",q[l]);
	} puts(""); l=1;r=0;
	for(int i=1;i<=n;i++) {
		while(l<=r && q[r]<=a[i]) r--;
		q[++r]=a[i]; p[r]=i;
		while(p[l]<=i-m) l++;
		if(i>=m) printf("%d ",q[l]);
	}  //这边同理
	return 0;
}

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/bifanwen/p/12652614.html