作為一名火星人，你為了佔領地球，需要想方設法使地球人失去信心。現在你獲得了一項能力，控制今後 \(n\) 天的天氣溫度，對於第 \(i\) 天,你能將溫度控制在 \([a_i,b_i]\) 中任意一個數位，你的目的是使其中某段時間，溫度持續不下降，趁此來攻擊地球。
現在問你最多可以使連續的多少天滿足溫度不下降。
第一行給出一個整數 \(n\)，表示你能控制的天數。
接下來 \(n\) 行,第 \(i\) 行給出 \(2\) 個整數 \(a_i,b_i\),表示你能控制的天氣範圍。保證 \(a_i\le b_i\)。
輸出一個整數，表示答案。
4
1 3
2 4
1 1
3 4
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;
}