题解 P2629 【好消息，坏消息】

· · 题解

震惊，一道单调队列好题就这样被浪费掉了？翻了半天题解结果发现用单调队列的没几个，极度悲哀，这道题用stl的双端队列一会就水过去了QWQ(STL大法好！！！嘿嘿）

补上一个双端队列的题解吧


#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;
inline int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f*x;
}//用处不大的快读
inline void write(int x){
    int s[50],p=0;
    if(x<'0'){putchar('-');x=-x;}
    do{s[p++]=x%10;x/=10;}while(x);
    for(int i=p-1;i>=0;i--)putchar(s[i]+'0');
    putchar('\n');
}//没用到的快输
int s[1000001],ans[1000001],f[2000002];
int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        s[i]=read();
        s[n+i]=s[i];
        f[i]=f[i-1]+s[i];//求前缀和~
    }
    for(int i=n+1;i<=n+n-1;i++){
        f[i]=f[i-1]+s[i];//这里我们可以把环转化链，就相当于把两个剪断的环接起来
    }
    deque<int>d;//方便的STL双端队列！！！
    d.push_back(1);
    for(int i=2;i<=2*n-1;i++){
        while(!d.empty()&&f[i]<f[d.back()])d.pop_back();d.push_back(i);
        while(!d.empty()&&i-d.front()>n)d.pop_front();
        if(i>=n)ans[i]=f[d.front()]-f[i-n];
    }//f[d.front()]-f[i-n]这里可能不大好明白QWQ,仔细想想，其实这就是运用了前缀和，也就是这个点和起点中间所有数的和?不大会说呢，仔细理解一下吧。
    int maxn=0;
    for(int i=n;i<=2*n-1;i++){
        if(ans[i]>=0)maxn++;
    }
    cout<<maxn<<endl;
}```
##话说为什么用STL的人那么少呀