hdu 4193 Non-negative Partial Sums

不断维护单调队列，从而实现最小值与初始值的比较来决定是否呈现 >= 零的情况

#include <cstdio>
int f,l,cnt;
int arr[2000010];
int num[2000010];
void in(int pos)
{
    while(f <= l && arr[ num[l] ] >= arr[pos]) --l;
    num[++l] = pos;
}
void out(int pos,int n)
{ 
    if(num[f] < pos-n) ++f;
    if(arr[ num[f] ] - arr[pos - n] >= 0) ++cnt;
}
int main()
{
   // freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n) != EOF)
    {
        if(!n) break;
        cnt = f  = 0;
        l = -1;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d",&arr[i]);
            arr[n+i] = arr[i];
            if(i) arr[i] += arr[i-1];
            in(i);
            if(i == n-1) out(i,n-1);
        }
        if(arr[n-1] < 0)
        {
            printf("0\n");
            continue;
        }
        for(int i = n; i < 2*n - 1; ++i)
        {
            arr[i] += arr[i-1];
            in(i);
            out(i,n-1);
        }
        printf("%d\n",cnt);
    }
    return 0;
}#in