一些知识点

单调队列是一个具有单调性的队列，常常被用来以 $O(n)$ 的复杂度维护移动的区间最值。

要点：

可以手动队列。
设定 head 和 tail 两个指针，head<=tail 成立则队列不为空。
维护单调性，双端队列。
维护时效性，过时弹出，否则压入。

模板

https://www.luogu.com.cn/problem/P1886。

对于任务一：

动态维护区间最小，维护一个单调递增序列。

单调性维护：把大于新加入元素的队尾元素都弹出，把新元素压入队尾。
时效性维护：队首元素若距离目前新加入的元素超过 $k$ 则弹出。
新的队首是区间最小。

手写

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define mset(a) memset(a,0,sizeof(a))
	const int N=1000000+10;
	struct Q{int pos,val;}q[N];
	int head,tail,n,k,a[N];
	void init(){mset(q),head=1,tail=0;}
	void yzmain()
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		init();
		for(int i=1;i<=n;i++)
		{
			while(head<=tail && q[tail].val>a[i]) tail--;
			q[++tail]=(Q){i,a[i]};
			while(i-q[head].pos>=k) head++;
			if(i>=k) printf("%d ",q[head].val);
		}
		printf("\n"),init();
		for(int i=1;i<=n;i++)
		{
			while(head<=tail && q[tail].val<a[i]) tail--;
			q[++tail]=(Q){i,a[i]};
			while(i-q[head].pos>=k) head++;
			if(i>=k) printf("%d ",q[head].val);
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

使用 STL deque

#include<bits/stdc++.h>
using namespace std;
namespace _deque
{
	const int N=1000000+10;
	struct Q{int pos,val;};
	deque<Q>qmax,qmin;
	int n,k,a[N];
	void yzmain()
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		for(int i=1;i<=n;i++)
		{
			while(!qmin.empty() && qmin.back().val>a[i]) qmin.pop_back();
			qmin.push_back((Q){i,a[i]});
			while(i-qmin.front().pos>=k) qmin.pop_front();
			if(i>=k) printf("%d ",qmin.front().val);
		}
		printf("\n");
		for(int i=1;i<=n;i++)
		{
			while(!qmax.empty() && qmax.back().val<a[i]) qmax.pop_back();
			qmax.push_back((Q){i,a[i]});
			while(i-qmax.front().pos>=k) qmax.pop_front();
			if(i>=k) printf("%d ",qmax.front().val);
		}
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_deque::yzmain();
	return 0;
}

P3957 [NOIP2017 普及组] 跳房子

题意

游戏规则：在地面上确定一个起点，然后在起点右侧画 $n$ 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在 Yurchiu 研发了一款机器人来参加这个游戏。它每次向右弹跳的距离只能为固定的 $d$ 。 Yurchiu 希望改进她的机器人，如果她花 $g$ 个金币改进他的机器人，那么她的机器人灵活性就能增加 $g$ 。每次弹跳的距离至少为 $1$ 。具体而言，机器人弹跳范围是从 $\max(1,d-g)$ 到 $d+g$ 的闭区间。

现在 Yurchiu 希望获得至少 $k$ 分，请问她至少要花多少金币来改造他的机器人。

点击查看题解

题解

二分答案

单调性分析：所花费金币具有单调性。花费高则灵活性高，从而得分高。

DP 验证

状态设计：f[i] 表示跳到第 $i$ 格所取得的最大分数。

无后效性分析：每次验证所花费金币一定，当前格的状态不会影响前面的状态。

状态转移方程： $f(i)=\max\{f(j)\}+a(i)$ ，其中 $j<i$ ， $a(i)$ 指 $i$ 点的分数。

单调队列优化

我们需要多一层循环来枚举 $j$ ，实际上在寻找最大的 $f(j)$ 。

维护一个单调递减序列。

单调性维护：使用一个指针来帮助压入符合的 $f$ 值。
若当前指针所指元素到当前所”DP“的元素的距离大于 $\max(1,d-g)$ ，把小于指针所指元素的队尾元素都弹出，把指针所指元素压入队尾。
时效性维护：队首元素若距离当前所”DP“的元素大于 $d+g$ 则弹出。
新的队首是要找的 $f(j)$ 。

代码

#include<bits/stdc++.h>
#define mset(f) memset(f,0,sizeof(f))
#define int long long
using namespace std;
const int N=500000+10;
struct P{int pos,score;}a[N];
struct Q{int pos,val;}q[N];
int n,d,k,f[N];
int head,tail;
int check(int g)
{
	int apos=0,l=max(1ll,d-g),r=d+g;
	head=1,tail=0;
	mset(q);
	for(int i=1;i<=n;i++)
	{
		f[i]=-2147483647114514;
		while(apos<i && a[i].pos-a[apos].pos>=l)
		{
			while(head<=tail && q[tail].val<f[apos]) tail--;
			q[++tail]=(Q){a[apos].pos,f[apos]};
			apos++;
		}
		while(head<=tail && a[i].pos-q[head].pos>r) head++;
		if(head<=tail) f[i]=max(f[i],q[head].val+a[i].score);
		if(f[i]>=k) return 1;
	}
	return 0;
}
#undef int
int main()
{
	#define int long long
	int l=1,r,mid;
	scanf("%lld%lld%lld",&n,&d,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i].pos,&a[i].score);
	r=max(a[n].pos,d);
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",l>a[n].pos?-1:l);
	return 0;
}

P2827 [NOIP2016 提高组] 蚯蚓

题意

蚯蚓长度 $x$ 为非负整数。 $n$ 个蚯蚓，切 $m$ 轮，每轮切一条最长的，切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓（ $p\in(0,1)$ ，有理数）。保留长度为 $0$ 的蚯蚓。除了本轮切的，其他蚯蚓每轮长度增加 $q$ 。求 $m$ 次被切蚯蚓的长度和 $m$ 轮后所有蚯蚓长度。

点击查看题解

题解

根据“运动的相对性”可以得到一些启发：其他蚯蚓变长，不就相当于被切的蚯蚓变短了吗！

记录累计加的长度，有几只没被加的就多减。

借助优先队列，可以写出 $O(nlogn)$ 的解（最多可以得到 $90$ 分）：

scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
for(ll i=1;i<=n;i++) scanf("%lld",a+i);
for(ll i=1;i<=n;i++) Q.push(a[i]);sum=0;//累计加的长度
for(ll i=1;i<=m;i++)
{
	ll now=Q.top()+sum;Q.pop();
	if(i%t==0) printf("%lld ",now);
	ll t1=now*u/v,t2=now-t1;sum+=q;//“多减”体现于此
	Q.push(t1-sum),Q.push(t2-sum);
}
printf("\n");u=1;
while(!Q.empty())
{
	ll now=Q.top();Q.pop();
	if(u%t==0) printf("%lld ",now+sum);u++;
}//Q 是 STL priority_queue。非常短有没有！

然而，这个题中有隐含的单调性**：先被切掉的蚯蚓分成的蚯蚓一定比后切掉**的蚯蚓分成的蚯蚓长。

所以，无需优先队列来维护单调性，因为它本来就是具有单调性的。省掉一个 log，得到 $O(n)$ 的正解。

维护 $3$ 个队列：初始队列，切出的左半部分蚯蚓队列，切出的右半部分蚯蚓队列。各队列都具有单调性（初始队列需要排序）。

但是，在考场上，与其费尽心思想 $100$ 分的正解，不如简简单单地花很少的时间得到 $90$ 分再考虑其他题。实际上，骗分是很重要的。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100000+10,inf=-2147483647;
ll n,m,q,u,v,t,a[N],now,sum=0;queue<ll>qs,qx,qn;
ll sele()
{
    ll a=inf,b=inf,c=inf,d;
    if(!qs.empty())a=qs.front();
    if(!qx.empty())b=qx.front();
    if(!qn.empty())c=qn.front();
    (d=max(a,max(b,c)))==a?qs.pop():(d==b?qx.pop():qn.pop());
    return d;
}
int main()
{
	scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
	for(ll i=1;i<=n;i++) scanf("%lld",a+i);
	sort(a+1,a+1+n,[](ll a,ll b)->bool{return a>b;});
	for(ll i=1;i<=n;i++) qs.push(a[i]);
	for(ll i=1;i<=m;i++)
	{
        now=sele()+sum;
		if(i%t==0) printf("%lld ",now);
		ll t1=now*u/v,t2=now-t1;sum+=q;
		qx.push(t1-sum),qn.push(t2-sum);
	}printf("\n");
	for(ll i=1;now=sele()+sum,i<=m+n;i++)
        if(i%t==0) printf("%lld ",now);
	return 0;
}

P5665 [CSP-S2019] 划分

本题解规模较大，已独立成篇：link。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/80519d42cd7c/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 二分动态规划单调队列队列

最后更新：2023-08-21, 23:18:21

By Yurchiu.