序列
题目背景
题目描述
作为一名火星人，你为了占领地球，需要想方设法使地球人失去信心。现在你获得了一项能力，控制今后 (n) 天的天气温度，对于第 (i) 天,你能将温度控制在 ([a_i,b_i]) 中任意一个数字，你的目的是使其中某段时间，温度持续不下降，趁此来攻击地球。
现在问你最多可以使连续的多少天满足温度不下降。
输入格式
第一行给出一个整数 (n)，表示你能控制的天数。
接下来 (n) 行,第 (i) 行给出 (2) 个整数 (a_i,b_i),表示你能控制的天气范围。保证 (a_ile b_i)。
输出格式
输出一个整数，表示答案。
样例 #1
样例输入 #1
4 1 3 2 4 1 1 3 4 样例输出 #1
2 提示
对于 (20%) 的数据 (3le nle10)；
对于 (40%) 的数据 (3le nle3000)；
对于 (60%) 的数据 (3le nle100000)；
对于 (100%) 的数据 (3le nle1000000)，(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("%dn",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("%dn",ans); return 0; } 
