A Huster

0%

单调队列

Posted on Edited on Valine:

前言

​ 单调队列并不是太难的东西,不应其应用到的题目困难而觉得单调队列困难.

​ 我第一次遇见单调队列时是在学图论时,遇到了Island这道题(见基环树专题),当时的我对单调队列一无所知,而对其优化更是懵,所以当时就懵着将题解半抄半写地打了出来,但还是不懂.现在来看,单论单调队列,它是不难的,难的是与其他算法的结合;

单调队列

限制与应用

​ 对于单调队列,有两个操作,入队和出队;

​ 有两个限制,队首元素满足区间条件,队列中数满足单调;

​ 应用限制,转移DP时应满足区间取max-min操作,即让单调有其发挥作用的空间;

入门

​ 推荐这道例题理解一下单调队列思想;

老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。

每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。

我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。

​ 我们首先考虑到答案是具有单调性的,宽度W满足条件,那么大于W的也会满足条件,那么我们可以二分答案;

​ 二分答案后,我们可以得到一个区间,我们想要的即所有区间中是否存在 $max-min>=D$ ;

​ 这里就引入了单调队列,单调队列的队首表示区间 $i-mid-1$ ~ $i$ 最大值或者最小值,其限制条件即 $q[l]>=i-mid-1$ ,不满足条件时弹出.

​ 入队时,比较队尾元素和要加入元素值,比较方式是 “比我小的人还比我强,那我就要退役了” ,即未来会更新到我们要加入值,存在时间肯定比队尾元素长,而队尾元素又比要加入的值小,那么队尾元素的贡献就可以被要加入的值代替,故直接弹出;

​ 那么这里我们限制一下区间,求出区间最大值与最小值,更新最大差值即可;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,inf=1e9;
int n,d,lim,q[maxn],f[maxn];
struct node{
	int x,y;
}a[maxn];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
	type_of_scan f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}

bool check(int mid){
	int l=1,r=0,x=1,y=0,ans=0;
	for(int i=1;i<=n;i++){
		int maxx=-1,minx=inf;
		while(l<=r&&a[q[l]].x<=a[i].x-mid-1) l++;//限制区间弹出,注意区间大小为mid+1 
		while(l<=r&&a[q[r]].y<=a[i].y) r--;//根据原则弹出 
		q[++r]=i;maxx=max(a[q[l]].y,maxx);//更新,下面是一样的 
		while(x<=y&&a[f[x]].x<=a[i].x-mid-1) x++;
		while(x<=y&&a[f[y]].y>=a[i].y) y--;
		f[++y]=i;minx=min(a[f[x]].y,minx);
		ans=max(maxx-minx,ans);
	}
	return ans>=d;
}

bool cmp(node a,node b){
	return a.x<b.x;
}

int main(){
	scan(n),scan(d);
	for(int i=1;i<=n;i++) scan(a[i].x),scan(a[i].y),lim=max(a[i].x,lim);
	sort(a+1,a+1+n,cmp);//排序 
	int l=1,r=lim;
	while(r>l){
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	if(!check(l)) puts("-1");
	else printf("%d\n",l);
}

​ 另一道例题 ,主要是依靠单调队列原则进行;

求一段最短的区间,其区间中包含了所有类型的颜色;

​ 根据题目中区间的信息,我们可以隐约地想到单调队列,但是并没有单调性.

​ 考虑队首弹出条件,当一个颜色在一个区间多次出现时,有贡献的只会是一个,那么当队首颜色重复时,其贡献已经被之后的颜色代替,也就没用了,那么既可以弹出;

​ 队尾弹出就不再需要了,我们直接更新满足条件的区间即可;

​ 那么思路即,对每种颜色计数,当队首元素颜色个数>=2时,将其弹出;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,cnt,num;
int q[1000007],ans=2147483647,vis[1000007];

struct node{
	int id,sp;	
}a[1000007];

bool operator <(node a,node b){
	return a.sp<b.sp;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int k=1,to;k<=m;k++){
		scanf("%d",&to);
		for(int i=1;i<=to;i++)
			scanf("%d",&a[++cnt].sp),a[cnt].id=k;
	}
	sort(a+1,a+n+1);
	int l=1,r=0;
	for(int i=1;i<=n;i++){
		if(vis[a[i].id]) vis[a[i].id]++;
		if(!vis[a[i].id]) vis[a[i].id]++,num++;
		while(vis[a[q[l]].id]>1) vis[a[q[l]].id]--,l++;//超过一个,弹出
		q[++r]=i;
		if(num==m) ans=min(ans,a[q[r]].sp-a[q[l]].sp);
	}
	printf("%d",ans);
	return 0;
}

进阶

​ 二维单调队列,在一个固定矩形中,求其中最大值和最小值.

例1

​ [HAOI2007]理想的正方形

在一个 $ab$ 的矩形中,求一个最大值与最小值差值最小的 $nn$ 的正方形,输出其差值;

​ 首先求出横向一维区间最大值,之后在原有横向区间最大值中求纵向一维区间最大值,这里由于用到了横向一维的值,使其变成了二维,那么思路就很显然了,注意区间大小和边界限制;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
int a,b,n,maps[1007][1007],work1[1007][1007],qmax[1007],qmin[1007],ans1[1007][1007];
int q[100007],work2[1007][1007],ans2[1007][1007],ans=2147483647;

int main(){
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			scanf("%d",&maps[i][j]);
		}
	}
	for(int x=1;x<=a;x++){
		int l=1,r=0,k=n;
		memset(qmax,0,sizeof(qmax));
		memset(qmin,0,sizeof qmin);
		for(int i=1;i<=b;i++){
			while(l<=r&&i-k>=qmax[l]) l++;
			while(l<=r&&maps[x][qmax[r]]<=maps[x][i]) r--;
			qmax[++r]=i;
			if(i>=n) work1[x][i-k+1]=maps[x][qmax[l]];
		}
		l=1,r=0,k=n;
		for(int i=1;i<=b;i++){
			while(l<=r&&i-k>=qmin[l]) l++;
			while(l<=r&&maps[x][qmin[r]]>=maps[x][i]) r--;
			qmin[++r]=i;
			if(i>=n) work2[x][i-k+1]=maps[x][qmin[l]];
		}
	}//横向区间最大最小值
	for(int x=1;x<=b;x++){
		int l=1,r=0,k=n;
		memset(qmax,0,sizeof(qmax));
		memset(qmin,0,sizeof qmin);
		for(int i=1;i<=a;i++){
			while(l<=r&&i-k>=qmax[l]) l++;
			while(l<=r&&work1[qmax[r]][x]<=work1[i][x]) r--;
			qmax[++r]=i;
			if(i>=n) ans1[i-k+1][x]=work1[qmax[l]][x];
		}
		l=1,r=0,k=n;
		for(int i=1;i<=a;i++){
			while(l<=r&&i-k>=qmin[l]) l++;
			while(l<=r&&work2[qmin[r]][x]>=work2[i][x]) r--;
			qmin[++r]=i;
			if(i>=n) ans2[i-k+1][x]=work2[qmin[l]][x];
		}
	}//纵向区间最大最小值
	for(int i=1;i<=a-n+1;i++){
		for(int j=1;j<=b-n+1;j++)
			ans=min(ans,ans1[i][j]-ans2[i][j]);
	}
	printf("%d",ans);
}

例2

​ [HAOI2007]修筑绿化带 ,

如果把公园看成一个 $M N$ 的矩形，那么花坛可以看成一个 $CD$ 的矩形，绿化带和花坛一起可以看成一个 $A*B$ 的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，

绿化带的肥沃度= $AB$ 块的肥沃度 $- CD$块的肥沃度

为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

​ 震惊!某HA省竟在同一年考了两道相同算法的题

​ 这道题看起来是求最大区间值和,但是如果我们先用二维前缀和预处理出 $CD$ 矩形的权值和,然后再限制在 $AB$ 的矩形中,即上面那道题,有些不同的是,花坛不能触碰边界,注意边界的划分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
int m,n,c,d,a,b,maps[1007][1007],num[1007][1007];
int qmin[1007],mms[1007][1007];
int work2[1007][1007],ans2[1007][1007],ans;

int main(){
	scanf("%d%d%d%d%d%d",&m,&n,&a,&b,&c,&d);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&maps[i][j]);
			num[i][j]=maps[i][j]+num[i-1][j]+num[i][j-1]-num[i-1][j-1];
		}
	}
	for(int i=c;i<=m;i++){
		for(int j=d;j<=n;j++){
			maps[i-c+1][j-d+1]=num[i][j]-num[i-c][j]-num[i][j-d]+num[i-c][j-d];
			if(i>=a&&j>=b) mms[i-a+1][j-b+1]=num[i][j]-num[i-a][j]-num[i][j-b]+num[i-a][j-b];
		}
	}
	for(int x=1;x<=m-1;x++){
		int l=1,r=0,k=b-d-1;
		memset(qmin,0,sizeof qmin);
		for(int i=2;i<=n;i++){
			while(l<=r&&i-k>=qmin[l]) l++;
			while(l<=r&&maps[x][qmin[r]]>=maps[x][i]) r--;
			qmin[++r]=i;
			if(i-k+1>=0) work2[x][i-k+1]=maps[x][qmin[l]];
		}
	}
	for(int x=1;x<=n-1;x++){
		int l=1,r=0,k=a-c-1;
		memset(qmin,0,sizeof qmin);
		for(int i=1;i<=m;i++){
			while(l<=r&&i-k>=qmin[l]) l++;
			while(l<=r&&work2[qmin[r]][x]>=work2[i][x]) r--;
			qmin[++r]=i;
			if(i-k+1>0) ans2[i-k+1][x]=work2[qmin[l]][x];
		}
	}
	for(int i=1;i<=m-a+1;i++){
		for(int j=1;j<=n-b+1;j++){
			ans=max(ans,mms[i][j]-ans2[i+1][j+1]);
		}
	}
	printf("%d",ans);
}

DP与单调队列

​ [SCOI2010]股票交易 ;

通过一段时间的观察，$\text{lxhgww}$ 预测到了未来 $T$ 天内某只股票的走势，第 $i$ 天的股票买入价为每股 $AP_i$ ，第 $i$ 天的股票卖出价为每股 $BP_i$（数据保证对于每个 $i$，都有 $AP_i > BP_i$ ），但是每天不能无限制地交易，于是股票交易所规定第 $i$ 天的一次买入至多只能购买 $AS_i$ 股，一次卖出至多只能卖出 $BS_i$ 股。

另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 $W$ 天，也就是说如果在第 $i$ 天发生了交易，那么从第 $i+1$ 天到第 $i+W$ 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 $\text{MaxP}$。

在第 $1$ 天之前，$\text{lxhgww}$ 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，$T$ 天以后，$\text{lxhgww}$ 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

​ 首先推出DP式子,设 $f[i][j]$ 为第 $i$ 天手持 $j$ 个股票是的最大收入,那么分类转移;

​ CASE1: 没有买股票, $f[i][j]=f[i-1][j]$

​ CASE2: 买了股票,但是有 $W$ 天的限制,所以转移应为 $f[i][j]=max(f[i-w-1][j-k] - k*AP_i ,f[i][j])$ ;

​ CASE3: 卖了股票, $f[i][j]=max(f[i-w-1][j+k]+k*BP_i , f[i][j])$ ;

​ 那么 $k$ 的枚举我们可以用单调队列优化掉,时间复杂度 $O(tm)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int t,m,w,f[2007][2007],q[2007],ans=-INT_MAX;
int max(int a,int b){return a > b ? a : b;}

int main(){
	scanf("%d%d%d",&t,&m,&w);
	memset(f,128,sizeof(f));//初始化最小值
	for(int i=1,ap,bp,as,bs;i<=t;i++){
		scanf("%d%d%d%d",&ap,&bp,&as,&bs);
		memset(q,0,sizeof q);
		for(int j=0;j<=as;j++) f[i][j]=-ap*j;
		for(int j=0;j<=m;j++) f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=w) continue;
		int l=1,r=0;
		for(int j=0;j<=m;j++){
			while(l<=r&&q[l]<j-as) l++;
			while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap) r--;
			q[++r]=j;
			if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
		}//买的时候从比自己股票少的转移,正序枚举 
		memset(q,0,sizeof q);
		l=1,r=0;
		for(int j=m;j>=0;j--){
			while(l<=r&&q[l]>j+bs) l++;
			while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp) r--;
			q[++r]=j;
			if(l<=r) f[i][j]=max(f[i][j],f[i-1-w][q[l]]+q[l]*bp-j*bp);
		}//卖的时候从比自己股票多的转移,倒序枚举 
	}
	printf("%d",f[t][0]);
	return 0;
}

总结

​ 单调队列可以有效处理区间最大最小值信息,这在DP方程转移过程中有重要意义,但在应用时应注意其应用范围,而不是盲目的套;

​ 应用时要注意细节问题,区间范围应卡好,出队时注意判断范围;

练习题

​ P2254 [NOI2005]瑰丽华尔兹 ;

TO BE CONTINUE
本站访问次数：