单调队列的练习题解

前言：

在上一篇学习记录中，单调队列给出了几道练习题，因为这两道题的算法以及思路相差无几（几乎可以算是双倍经验quq），所以就在这里集中写一下相关的题解

前置知识：

见：队列专题（queue、priority_queue、deque） qvq

切蛋糕：

洛谷P1714

• 题目简述：
  给定n个元素的值Pi，窗口最大限度m，要求找出连续k（0<=k<=m）个元素，使得这些元素和最大，输出这个最大值

• 数据范围：
  对100%的数据，M≤N≤500000，|Pi|≤500。 答案保证在2^31-1之内

• 算法：
  单调队列deque&前缀和

• 解题思路：

（1）看到求连续一段区间最大值问题，便想到了用前缀和来维护，再循环模拟k的取值，然后每次用ans来比较取最大值

（2）打出纯前缀和代码，会得到40pts，其它意料之中的T掉，说明肯定还有其他算法

（3）我们需要维护长度为k的最大前缀和，所以想到了使用单调队列（好勉强啊...说实话不看算法标签我肯定想不到）

（4）单调队列的实现：当队尾存储的前缀和大于当前前缀和时，将当前前缀和存入队列中（因为计算前缀和需要减去前面的，不好理解可以看代码），再判断当前队首元素是否在窗口限度以内，最后用ans比较存储最大值再输出即可

• 代码Code：

（1）40pts的纯前缀和代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,ans,a[1000001],sum[1000001];

int main() {
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(register int k=1;k<=m;k++) {
        for(register int i=k;i<=n;i++) {
            ans=max(ans,sum[i]-sum[i-k]);
        }
    }
    printf("%d",ans);
    return 0;
}

（2）AC的前缀和+单调队列代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,ans,a[5000001],sum[5000001];

deque<int> shan;

int main() {
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(register int i=1;i<=n;i++) {
        while(!shan.empty()&&sum[shan.back()]>sum[i]) shan.pop_back();
        shan.push_back(i);
        while(shan.front()<i-m) shan.pop_front();
        ans=max(ans,sum[i]-sum[shan.front()]);
    }
    printf("%d",ans);
    return 0;
}

好消息，坏消息：

洛谷P2629

• 题目简述：
  给定n个消息的好坏度Ai，要求找出所有满足在告诉Boss全部消息过程中老板心情一直不低于0的方案总数

• 数据范围：
  对于100%数据n<=10^6，-1000 <= Ai <= 1000

• 算法：
  前缀和&单调队列deque

• 解题思路：
  （1）还是先暴力一发，能得到75pts，因为时间复杂度是O(n^2)，所以考虑优化

（2）因为是区间，所以还要使用前缀和来维护区间最值

（3）但是这道题并不是单独的求某一区间的最值，而是要求某一区间内的前缀和都不小于0，所以我们会想到合并石子的思路：破环为链

（4）开两倍数组，复制一遍前n个数，这样方便我们枚举所有情况，然后使用单调队列求出某一区间内的前缀和的最小值，再判断减去前面的前缀和后是否小于0，不是的话方案数++，于是我们就有了A掉这道题的满分思路

• 代码Code：

（1）75pts的暴力前缀和：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}//读取正负号
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}//x<<3=x*8,x<<1=x*2,合起来便是x*10了
    return x*f;
}
int n;
int a[2000005];
int sum[2000005];
bool check(int now) {
    for(register int j=0; j<n; j++) {
        if(sum[now+j]-sum[now-1]<0) return false;
    }
    return true;
}
int main() {
    n=read();
//  scanf("%d",&n);
    for(register int i=1; i<=n; i++) {
        a[i]=read();
//      scanf("%d",&a[i]);
        a[i+n]=a[i];
        sum[i]=sum[i-1]+a[i];
    }
    int tot=1;
    for(register int i=n+1; i<=2*n-1; i++) {
        sum[i]=sum[i-1]+a[tot];
        tot++;
    }
    int ans=0;
    for(register int i=1; i<=n; i++) {
        if(check(i)==true) ans++;
    }
    printf("%d",ans);
    return 0;
}

（2）单调队列+前缀和的满分代码：

#include <bits/stdc++.h>
using namespace std;
int n,ans,a[2000010],sum[2000010];

deque<int> shan;

int main() {
    scanf("%d",&n);
    for(register int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        a[i+n]=a[i]; //破环为链 
    }
    for(register int i=1;i<2*n;i++) sum[i]=sum[i-1]+a[i]; //记录前缀和 
    for(register int i=1;i<2*n;i++) { //枚举 
        while(!shan.empty()&&sum[shan.back()]>=sum[i]) shan.pop_back(); //deque来维护前缀和最小值 
        shan.push_back(i);
        if(i>=n) { 
            while(!shan.empty()&&shan.front()<i-n) shan.pop_front(); //处理队首元素超过窗口最大限度的情况（本题窗口限度就是n） 
            if(sum[shan.front()]>=sum[i-n]) ans++; //如果满足条件，方案数++ 
        }
    }
    printf("%d",ans);
    return 0;
} 

吐槽一下：我真的是炒鸡炒鸡蒻啊啊啊啊！！！第二个做法的代码里面前缀和只记录了前n个数的前缀和（晕）...结果...结果...调了半个多小时求助旁边的WS大佬才发现（我去QAQ）

再来一发WS大佬的题解：好消息，坏消息