P2629 好消息，坏消息

主思想就是对每个 $k$ ，判断是否可行。

(1):

对于每个 $k$ ，首先判断 $a[k],a[k+1],...,a[n]$ 是否满足。

考虑到可以递推，将 $k$ 从 $n$ 到 $1$ 循环，

用 $f[k]$ 表示 $s[k],s[k+1],...,s[n]$ 的最小值

（ $s[i]=a[k]+a[k+1]+...+a[i],i=k,k+1,...,n$ ）

则易得 $f[k]=min(a[k],a[k]+f[k+1])$

那么得到了 $f[k]$ ，只需判断 $f[k]$ 是否不小于 $0$ 即可。

(2):

后半部分对于 $a[1],a[2],...,a[n]$ 的判断则更加简单。

预处理 $mis[i]=min(s[1],s[2],...,s[i])$ ， $i=1,2,...,n$

其中 $s[k]=a[1]+a[2]+...+a[k],k=1,2,...,n$

那么只要判断 $mis[k]+a[k]+a[k+1]+...+a[n]$ 是否不小于 $0$ 即

可。

总复杂度 $O(n)$

#include<iostream>
#include<cstdio>
int read();
#define maxn 1000010
#define miin(a,b) ((a)<(b)?(a):(b))
using namespace std;

int n;
int a[maxn],s[maxn],mis[maxn];
int main(){
    n=read();
    mis[0]=2000000000;
    for(int i=1;i<=n;i++){
        a[i]=read();
        s[i]=s[i-1]+a[i];
        mis[i]=miin(mis[i-1],s[i]);
    }mis[0]=0;
    int no=0,Ans=0;
    for(int k=n;k>=1;k--){
        no=miin(a[k],no+a[k]);
        if(no>=0&&mis[k-1]+s[n]-s[k-1]>=0)Ans++;
    }
    cout<<Ans;
    return 0;
}
int read(){
    int s=0,k=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*k;
}

单调队列做法待补完（给自己讲的，请忽略此句）