hdu 4193 Non-negative Partial Sums 单调队列

先复制一遍数组，在用一个数组sum[ i ]表示前 i 个数字的和，对于以第k个数开头的情况，只需找出sum[ k ]到sum[ k+n ]的最小值min，如果min - sum[ k-1 ]大于0则满足。

#include <stdio.h>
#define maxn 2001000
int a[maxn],sum[maxn];
int q[2*maxn];
int n;
int front,rear;
void in(int i)
{
   while(front<=rear&&sum[q[rear]]>=sum[i]) rear--;
   q[++rear]=i;
}
int out(int i)
{
    if(q[front]==i-n) front++;
    return q[front];
}
int main()
{
    int i;
    while(1)
    {
        int ans=0;
        scanf("%d",&n);
        if(n==0) break;
        a[0]=0;
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for(i=n+1;i<=2*n;i++)
        {
            a[i]=a[i-n];
            sum[i]=sum[i-1]+a[i];
        }
        front=0;rear=-1;
        for(i=1;i<n;i++)
            in(i);
        for(i=n;i<2*n;i++)
        {
            in(i);
            int u=out(i);
            if((sum[u]-sum[i-n])>=0)
                ans++;
        }
        printf("%d
",ans);
    }
    return 0;
}