単調な隊列-hdu-423-Non-negative Partal Sums

テーマリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4193
タイトルの大意:
n個の数をあげて、a 0,a 1,…an,ai＋1,…an,a 1,a 2,…ai-1のような配列のシードは、すべての前k(1==k<=n)個の合計が0以上になるようにする.
問題解決の考え方:
プレフィックスと、シーケンスをダブルクリックします.
前のk個と都>=0を満たすには最小値>=0だけが必要ですので、最小のプレフィックスとsum[i],(i>=j-n＋1)を単調な列で維持するとsum[j]-sum[i]が一番大きいことが保証されますので、区間【j-n＋1,i】が一番小さいです.
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-6
#define INF 0x3fffffff
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 1100000
int sum[Maxn<<1];
int q[Maxn];

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   int n;

   while(scanf("%d",&n)&&n)
   {
       sum[0]=0;
       for(int i=1;i<=n;i++) //    ，     
       {
           scanf("%d",&sum[i]);
           sum[i+n]=sum[i];
           sum[i]+=sum[i-1];
       }
       for(int i=n+1;i<2*n;i++)
           sum[i]+=sum[i-1];
       int head=0,tail=-1,ans=0; //      
       //q[0]=0;
       for(int i=1;i<2*n;i++)
       {
           while(head<=tail&&sum[i]<=sum[q[tail]])
                tail--;
            q[++tail]=i;// i  
            while(q[head]<i-n+1)
                head++;
            if(i>=n) //     
            {
                int t=sum[i]-sum[q[head]]; //     
                if(sum[i]-sum[i-n]-t>=0) //       ，       0 ，
                    ans++;               //        
            }
       }
       printf("%d
",ans);
   }

   return 0;
}