本次训练共7题,本文附AC代码和题目链接。

先介绍C++的STL中双端队列的使用方法。
定义双端队列deque<int>q;
双端队列对队首和队尾都可以进行操作,具体如下:

q.push_front(x);//x入队首
q.push_back(x);//x入队尾
q.pop_front();//删除队首元素
q.pop_back();//删除队尾元素

洛谷 P1714 切蛋糕

用前缀和预处理,用单调队列维护[i-m,i]区间内前缀和的最小值,
(实际上求和区间是[i-m+1,i],但是这个区间内的和用sum数组表示为sum[i]-sum[i-m],即把sum的区间看成[i-m,i])
则每次遍历的区间内所有元素和的最大值为sum[i]-sum[q.front()],找出sum[i]-sum[q.front()]的最大值即可。

先来个错误示范(在洛谷上虽然能AC,但是实际上是错的)

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,x,mx,sum[N];
deque<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&i-q.front()>=m+1)q.pop_front();
        while(!q.empty()&&sum[q.back()]>sum[i])q.pop_back();
        q.push_back(i);
        mx=max(mx,sum[i]-sum[q.front()]);
    }
    printf("%d\n",mx);
    return 0;
}

hack数据:

输入
6 3
3 4 5 -4 -5 -6
输出
12

错误输出:9
错误原因:没考虑减去sum[0]的情况
解决办法:i从0开始循环

输入
6 3
-1 -1 -1 -1 -1 -1
输出
-1

错误输出:0
错误原因:会漏掉单个数是最大值的情况
解决办法:把取mx的位置移到第一个while之后(即先取滑动窗口区间内的sum最小值,之后再维护单调性)

AC代码(原题链接:LOJ #10176. 「一本通 5.5 例 2」最大连续和

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10,inf=(1<<31)-1;
int n,m,mx,x,sum[N];
deque<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    mx=-inf;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    for(int i=0;i<=n;i++)//i从0开始
    {
        while(!q.empty()&&i-q.front()>=m+1)q.pop_front();//弹出旧区间的点
        if(!q.empty())mx=max(mx,sum[i]-sum[q.front()]);//取最大值的位置放在第一个while后面
        while(!q.empty()&&sum[i]<sum[q.back()])q.pop_back();//维护,使队列单调
        q.push_back(i);
    }
    printf("%d\n",mx);
    return 0;
}

洛谷 P1440 求m区间内的最小值

维护一个单调递增的双端队列,用ans数组记录队首元素,ans[i]表示a[i]及其之前的m-1个元素中(共m个元素)的最小值,所以最后输出ans[0]~ans[n-1]即可。

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,a[N],ans[N];
deque<int>q;//定义双端队列q,用来存放下标i
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&i-q.front()>=m)//若队首元素与现在遍历的元素下标之差大于等于m,则删除队首元素
            q.pop_front();
        while(!q.empty()&&a[q.back()]>a[i])//若队尾元素大于现在遍历的元素,说明现在出现了比之前小的值,则删除队尾元素
            q.pop_back();
        q.push_back(i);
        ans[i]=a[q.front()];
    }
    for(int i=0;i<=n-1;i++)
        printf("%d\n",ans[i]);
    return 0;
}

洛谷 P2032 扫描

维护一个单调递减队列,也就是维护[i-m+1,i]区间内a[i]的最大值(即队列队首元素)。

#include <bits/stdc++.h>
const int N=2e6+10;
using namespace std;
int n,m,a[N],ans[N];
deque<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&i-q.front()>=m)
            q.pop_front();
        while(!q.empty()&&a[q.back()]<a[i])
            q.pop_back();
        q.push_back(i);
        ans[i]=a[q.front()];
    }
    for(int i=m;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

洛谷 P1886 滑动窗口

维护两个单调队列,一个递增,一个递减,开两个数组分别记录两个队列的队首元素,最后注意从下标m开始输出答案。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N],mi[N],mx[N];
deque<int>q1,q2;//q1为递增队列,q2为递减队列
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!q1.empty()&&i-q1.front()>=m)
            q1.pop_front();
        while(!q1.empty()&&a[q1.back()]>a[i])
            q1.pop_back();
        q1.push_back(i);
        while(!q2.empty()&&i-q2.front()>=m)
            q2.pop_front();
        while(!q2.empty()&&a[q2.back()]<a[i])
            q2.pop_back();
        q2.push_back(i);
        mi[i]=a[q1.front()];
        mx[i]=a[q2.front()];
    }
    for(int i=m;i<=n;i++)
    i==n?printf("%d\n",mi[i]):printf("%d ",mi[i]);
    for(int i=m;i<=n;i++)
    i==n?printf("%d\n",mx[i]):printf("%d ",mx[i]);
    return 0;
}

洛谷 P2629 好消息,坏消息

断环为链,把a[1]~a[n-1]接在a[n]之后,形成一个长度为2*n-1的序列,滑动窗口长度为n。
前缀和预处理,用单调队列维护前缀和的最小值,[i-m,i]区间内sum最小值为sum[q.front()],只要保证该区间内和的最小值sum[q.front()]-sum[i-n]>=0,则可以保证在[i-m+1,i]区间内所有元素和或者部分元素和都大于等于0。

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,ans,a[N],sum[N];
deque<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=n+1;i<=2*n-1;i++)
    {
        a[i]=a[i-n];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=2*n-1;i++)
    {
        while(!q.empty()&&i-q.front()>n)//没有等于号
            q.pop_front();
        while(!q.empty()&&sum[q.back()]>sum[i])
            q.pop_back();
        q.push_back(i);
        if(i>=n&&sum[q.front()]-sum[i-n]>=0)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

洛谷 P1725 琪露诺

单调队列优化DP。
用dp[i]表示到达i位置时的和,滑动窗口长度为m=r-l+1,用单调队列维护dp值的滑动窗口,最后在[n-r+1,n]区间内找到dp最大值即为答案。注释详见代码。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int n,m,l,r,mx,a[N],dp[N];
deque<int>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>l>>r;
    m=r-l+1;//m为滑动窗口大小
    for(int i=0;i<=n;i++)
        cin>>a[i];
    memset(dp,-inf,sizeof(dp));//注意dp初始化为最小值
    dp[0]=0;
    for(int i=0;i<=n-l;i++)
    {
        while(!q.empty()&&i-q.front()>=m)q.pop_front();
        while(!q.empty()&&dp[q.back()]<dp[i])q.pop_back();
        //维护一个递减队列,队首为[i-m+1,i]区间内dp的最大值
        q.push_back(i);
        dp[i+l]=dp[q.front()]+a[i+l];//dp[i+l]表示跳到i+l位置时的最大和
    }
    mx=-inf;
    for(int i=n-r+1;i<=n;i++)
        mx=max(mx,dp[i]);
    printf("%d\n",mx);
    return 0;
}

洛谷 P2422 良好的感觉

洛谷数据很水,写了个O(n^2^)的暴力竟然也能AC...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,l,r,mx,a[N],sum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        l=r=i;
        while(l>=1)
        {
            if(a[l-1]>a[i])l--;
            else break;
        }
        while(r<=n)
        {
            if(a[r+1]>a[i])r++;
            else break;
        }
        mx=max(mx,a[i]*(sum[r]-sum[l-1]));
    }
    printf("%lld\n",mx);
    return 0;
}

然而,1e5的数据规模,要避免TLE,只能写O(n)或者O(nlogn)的算法。

推荐做数据不水的原题:POJ 2796 Feel Good

开l、r两个数组记录a[i]作为区间[ l [i] , r [i] ]内的最小值最远能扩展到的左端点l[i]和右端点r[i],正逆遍历各一次,用两个双端队列分别求出 l [i] 和 r [i],最后找最大值及其左右端点即可。
至于如何用单调队列的思想得到 l、r 数组,再详细说明一下。以找 r[i] 为例,遍历1~n,每次保证队尾是队列中的最小值,如果不是,则队尾出队,并记录以队尾为最小值时能扩展到的最远的右端点,遍历完之后剩下的队列中所有的位置对应的右端点都是n,比如说a[q.back()]是区间[q.back(),n]内的最小值,即r[q.back()]=n。
不知道为什么cin前面加了ios::sync_with_stdio(false)还是超时,改成scanf就好了,可能是POJ这题Special Judge的锅...
以下给出O(n)算法的单调队列优化代码:

#include <deque>
#include <cstdio>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n,mx,ansl,ansr,a[N],l[N],r[N],sum[N];
deque<ll>q1,q2;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        while(!q1.empty()&&a[q1.back()]>a[i])//每次保证队尾是队列中的最小值,如果不是,则队尾出队,并记录以队尾为最小值时所能扩展到的右端点
        {
            r[q1.back()]=i-1;
            q1.pop_back();
        }
        q1.push_back(i);
    }
    while(!q1.empty())//剩下的队列中所有位置对应的右端点都是n
    {
        r[q1.back()]=n;
        q1.pop_back();
    }
    for(int i=n;i>=1;i--)
    {
        while(!q2.empty()&&a[q2.back()]>a[i])
        {
            l[q2.back()]=i+1;
            q2.pop_back();
        }
        q2.push_back(i);
    }
    while(!q2.empty())
    {
        l[q2.back()]=1;
        q2.pop_back();
    }
    mx=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]*(sum[r[i]]-sum[l[i]-1])>=mx)//注意有等于号,从而保证a[i]全部等于0的情况也会记录ansl和ansr
        {
            mx=a[i]*(sum[r[i]]-sum[l[i]-1]);
            ansl=l[i];
            ansr=r[i];
        }
    }
    printf("%lld\n%lld %lld\n",mx,ansl,ansr);
    return 0;
}

做完我们发现只对双端队列的尾部进行了操作,所以这题也可以用栈来解决,也就是所谓的“单调栈”。