单调队列专题题解

(T1:[POI2010]PIL-Pilots)

题意:给定(n,k)和一个长度为(n)的序列，求最长的最大值最小值相差不超过(k)的序列的长度.

分析:维护两个单调队列,一个维护最大值,一个维护最小值,每次更新前先检查两个队列的队头的下标是否相差在(k)以内,如果大于则令下标较小的队头出队,同时记录当前出队的下标最小值,用于后面更新答案.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e6+5;
int k,n,a[N],q1[N],q2[N];
int main(){
	k=read();n=read();for(int i=1;i<=n;++i)a[i]=read();
	int l1=1,r1=0,l2=1,r2=0,ans=0,last=0;
	for(int i=1;i<=n;++i){
		while(l1<=r1&&a[i]>a[q1[r1]])--r1;q1[++r1]=i;
		while(l2<=r2&&a[i]<a[q2[r2]])--r2;q2[++r2]=i;
		while(a[q1[l1]]-a[q2[l2]]>k){
			if(q1[l1]<q2[l2])last=max(last,q1[l1]),++l1;
			else if(q1[l1]>q2[l2])last=max(last,q2[l2]),++l2;
		}
		ans=max(ans,i-last);
	}
	printf("%d
",ans);
	return 0;
}

(T2:Cash) (back)

洛咕

题意:你需要把一个长度为(n)的序列任意分段,每一段假设长度为k，就去掉前(lfloorfrac{k}{m} floor) 小的数,最小化剩下的数的和.

分析:假设我们选择了一个长度为(2m)的段([1,2m]),所以要去掉这一段的最小值(min1)和次小值(min2),段的中点是(m),这两个值要么都在中点的同一侧,要么分别在中点的两侧.

如果两个值在中点的两侧,即(min1)是([1,m])的最小值,(min2)是([m+1,2m])的最小值.那么我们把这一段拆成两段([1,m])和([m+1,2m]),再选最小值,产生的贡献是一样的.

如果两个值在中点的同侧,假设都在([1,m])这一段,那么([m+1,2m])这一段的最小值比(min1,min2)都要大,所以此时我们把这一段拆成两段([1,m])和([m+1,2m]),再选最小值,能够更优.

综上这个序列要么拆成长度为(m)的段产生一个最小值的贡献,要么拆成长度小于(m)的段,然后长度小于(m)的段反正不会产生贡献,就可以看做是若干个长度为(1)的段.

所以可以单调队列预处理出(g[i])表示([i-m+1,i])的最小值.然后设(f[i])表示考虑到序列的第(i)位的答案,则(f[i]=min(f[i-1]+a[i],f[i-m]+sum[i]-sum[i-m]-g[i])).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
int n,m,a[N],q[N],g[N];
ll sum[N],f[N];
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i)a[i]=read(),sum[i]=sum[i-1]+a[i];
	int l=1,r=0;
	for(int i=1;i<=n;++i){
		while(l<=r&&a[i]<=a[q[r]])--r;
		q[++r]=i;
		while(l<=r&&i-q[l]+1>m)++l;
		g[i]=a[q[l]];
	}
	for(int i=1;i<=n;++i){
		f[i]=f[i-1]+a[i];
		if(i-m>=0)f[i]=min(f[i],f[i-m]+sum[i]-sum[i-m]-g[i]);
	}
	printf("%lld
",f[n]);
    return 0;
}

(T3:[NOI2005])瑰丽华尔兹

题意:

(T4: [USACO12MAR])花盆(Flowerpot)

洛咕

分析:显然花盆的长度是可以二分答案的.设当前二分的答案为(mid),将水滴按照横坐标从小到大排序,然后就分别求以每个水滴的横坐标为右端点,长度为(mid)的这一段区间 所包含的水滴的纵坐标的最值.

最大值和最小值分别维护两个单调队列来求即可.如果存在一个(i),使得(maxn[i]-minn[i]>=m),则是一次合法的二分答案.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
int n,m,maxn,minn=1<<30,f[N],g[N],q[N];
struct node{int x,y;}a[N];
inline bool cmp(node x,node y){return x.x==y.x?x.y<y.y:x.x<y.x;}
inline bool check(int mid){
	int l=1,r=0;
	for(int i=1;i<=n;++i){
		while(l<=r&&a[i].y<=a[q[r]].y)--r;
		q[++r]=i;
		while(l<=r&&a[i].x-a[q[l]].x>mid)++l;
		f[i]=a[q[l]].y;
	}
	l=1,r=0;
	for(int i=1;i<=n;++i){
		while(l<=r&&a[i].y>=a[q[r]].y)--r;
		q[++r]=i;
		while(l<=r&&a[i].x-a[q[l]].x>mid)++l;
		g[i]=a[q[l]].y;
	}
	for(int i=1;i<=n;++i)if(g[i]-f[i]>=m)return 1;
	return 0;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i){
		a[i].x=read(),a[i].y=read();
		minn=min(minn,a[i].y);maxn=max(maxn,a[i].y);
	}
	if(maxn-minn<m){puts("-1");return 0;}
	sort(a+1,a+n+1,cmp);
	int l=0,r=1000000,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d
",ans);
    return 0;
}