序列 方法记录

时间:2022-10-14 21:04:31

题目背景

题目描述

作为一名火星人,你为了占领地球,需要想方设法使地球人失去信心。现在你获得了一项能力,控制今后 \(n\) 天的天气温度,对于第 \(i\) 天,你能将温度控制在 \([a_i,b_i]\) 中任意一个数字,你的目的是使其中某段时间,温度持续不下降,趁此来攻击地球。

现在问你最多可以使连续的多少天满足温度不下降。

输入格式

第一行给出一个整数 \(n\),表示你能控制的天数。

接下来 \(n\) 行,第 \(i\) 行给出 \(2\) 个整数 \(a_i,b_i\),表示你能控制的天气范围。保证 \(a_i\le b_i\)

输出格式

输出一个整数,表示答案。

样例 #1

样例输入 #1

4
1 3
2 4
1 1
3 4

样例输出 #1

2

提示

对于 \(20\%\) 的数据 \(3\le n\le10\)

对于 \(40\%\) 的数据 \(3\le n\le3000\)

对于 \(60\%\) 的数据 \(3\le n\le100000\)

对于 \(100\%\) 的数据 \(3\le n\le1000000\)\(1<=a_i,b_i<=100000\)

题解

通过对题意的理解,不难想出\(O(n^2)\)的暴力做法。

枚举从每一天开始,能得到的最大温度不下降天数。

对于枚举的每一天,我们可以用贪心的思想来使温度不下降天数尽可能大。

\(i\)天的温度下限、上限分别为\(a[i]\)\(b[i]\).要使温度不下降天数尽可能大,那么每一天的温度就应该在控制能力范围内尽可能小。记录一个第\((i-1)\)天的最小温度\(tem\)\(tem\)的初值为\(0\)),那么对于第\(i\)天,若\(b[i]>=tem\)则说明你有能力使温度不下降,这里就可以对答案作出贡献了。在此基础上,若\(a[i]>=tem\),则将\(a[i]\)的值赋给\(tem\)来使\(tem\)在允许的前提下尽可能小。最终的答案就是以每一天为起点最大不下降天数的最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005;
int n,ans,tem,tmp;
int a[N],b[N];
int maxx(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(int l=1;l<=n;l++)
	{
		tmp=0;
		tem=0;
		for(int i=l;i<=n;i++)
		{
			if(b[i]>=tem)
			{
				tmp++;
				if(a[i]>=tem) tem=a[i];
			}
			else break;
		}
		ans=maxx(ans,tmp);
	}
	printf("%d\n",ans);
	return 0;
}

考虑正解

回忆一下我们暴力做法外层循环做的工作,可以概括为“从第\(i\)天开始有多少天能维持不下降”,这一步体现的单调性不禁让人想起单调队列

可以看看我写的这篇单调队列的模板题。

不如让我们先来重温一下滑动窗口吧。

下面的代码块可以处理出窗口最小值:

for(int i=1;i<=n;i++)//窗口最小值 
{
	while(h<=t&&i-q1[h]>=k) h++; 
	while(h<=t&&a[i]<a[q1[t]]) t--;
	q1[++t]=i;
	if(i>=k) printf("%d ",a[q1[h]]);
}

一行一行地加以理解。

while(h<=t&&i-q1[h]>=k) h++; 

实现窗口移动。

while(h<=t&&a[i]<a[q1[t]]) t--;

这是对已经入队的老成员的“考验”,这一步决定了老成员的去或留。

q1[++t]=i;

这是新成员入队的“机会”。有趣的是,新成员的机会往往伴随着对老成员的考验,或者说新成员入队本身就是对老成员的考验。一旦有老成员在“有生之年”都不如某即将入队的新成员,那老成员就该出队了。

再回到这道题。

程序设计上来讲,最外层循环还是用于枚举每一天,但内层我们可以使用单调队列来处理温度不下降的天数。

单调队列的核心,就是确定“机会”与“考验”。

下面我们用\(l\)来表示开始的天数\(r\)来表示尝试能够维持温度不下降的下一天。由于单调队列的单调性,上文的\(tem\)就是\(a[q[h]]\),即队首元素\(q[h]\)\(a\)数组的下标。(顺便一提,单调队列中的\(q\)数组一般都存的是位置信息而不会存值)

判断能否入队。若\(b[r]>=a[q[h]]\),则有新队员可以入队;并且若老成员(依次枚举队尾)的大小比不上新一天的最小温度,即\(a[q[t]]<a[r]\),则出队。下面就是核心代码了:

while(r<=n&&b[r]>=a[q[h]])
{
	while(h<=t&&a[q[t]]<a[r]) t--;//老成员出队 
	q[++t]=r++;//新成员入队 
}

另外本题还有一些细节需要处理。

如,需确保队首元素大于等于\(l\),因为我们分析的是第\(l\)天及以后的日子。

while(h<=t&&q[h]<l) h++;

又如,当\(r<=l\)时,说明经历了一次维持温度不下降失败,需要从失败的位置开始再次尝试之后能维持的天数。

if(r<=l)
{
	r=l+1;
	q[++t]=l;
}

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
const int N=1000001;
int n,ans;
int a[N],b[N],q[N];
int maxx(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	q[1]=1;
	int h=0,t=0;
	for(int l=1,r=2;l<=n&&r<=n;l++)//从l开始有多少天能维持不下降 
	{
		while(h<=t&&q[h]<l) h++;
		if(r<=l)
		{
			r=l+1;
			q[++t]=l;
		}
		while(r<=n&&b[r]>=a[q[h]])
		{
			while(h<=t&&a[q[t]]<a[r]) t--;//老成员出队 
			q[++t]=r++;//新成员入队 
		}
		ans=maxx(ans,r-l);
	}
	printf("%d\n",ans);
	return 0;
}

参考