P3512 [POI2010]PIL-Pilots 单调队列的应用

题目描述

给定n,k和一个长度为n的序列，求最长的最大值最小值相差不超过k的序列

输入格式

第一行两个有空格隔开的整数k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表设定的最大值，n代表序列的长度。第二行为n个由空格隔开的整数ai（1<=ai<=2000,000,000），表示序列。

输出格式

一个整数代表最大的符合条件的序列

首先解释一下题目：这道题让我们求出一个长度为n的序列中最长的一段子序列，满足这段子序列的最大值减最小值的差不超过k，求子序列的最大长度。
因为单调队列可以记录下一段区间的最大值和最小值，所以这道题我们完全可以用一个单调队列来实现。

我们设立一个l和r变量，分别表示子区间的左边界和右边界。接下来我们对任意一个子序列进行移动：
移动操作有两种情况，第一种即当该单调区间的最大值减去最小值的差小于等于k时，该单调区间是一个合法的区间。这时我们可以对答案进行记录，然后让r++，再进行判断是否会有更大的区间。

第二种情况，即当该单调区间的最大值减去最小值的差大于k时，该区间是一个不合法的区间。这时候我们不能将r++，因为这种操作不可能减小该区间内的最大值或增大该区间内的最小值，使变成一个合法的区间。我们只能将l++，然后注意要根据之前的a[l]和maxn，minn之间关系的三种情况对最大值和最小值进行维护。注意，单调队列是单调的，它只能往右移动，绝对不能出现往左移动的状况，即绝对不能l--或r--

这样我们就成功维护了单调队列的操作。

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int k,n,l,r,maxn,minn,ans;
int a[3000005];
void find(int l,int r){
    maxn=-inf;minn=inf;
    for(int i=l;i<=r;i++){
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
}
int main(){
    cin>>k>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    l=1;r=2;
    maxn=max(a[1],a[2]);
    minn=min(a[1],a[2]);
    while(1){
        if(maxn-minn>k){
            if((a[l]==minn)||(a[l]==maxn)){
                l++;
                find(l,r);
            }else if(a[l]>minn){
                l++;
            }
        }else{
            r++;
            if(a[r]<minn){
                minn=a[r];
            }else if(a[r]>maxn){
                maxn=a[r];
            }
            if(maxn-minn<=k){
                ans=max(ans,r-l+1);
            }
        }
        if(r==n){
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}