题目背景
题目描述
作为一名火星人,你为了占领地球,需要想方设法使地球人失去信心。现在你获得了一项能力,控制今后 \(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;
}