序列
题目背景
题目描述
\(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;
}