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