hdu 4193 Non-negative Partial Sums 单调队列。

Non-negative Partial Sums

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1420 Accepted Submission(s): 544

Problem Description

You are given a sequence of n numbers a₀,..., a_n-1. A cyclic shift by k positions (0<=k<=n-1) results in the following sequence: a_k a_k+1,..., a_n-1, a₀, a₁,..., a_k-1. How many of the n cyclic shifts satisfy the condition that the sum of the fi rst i numbers is greater than or equal to zero for all i with 1<=i<=n?

Input

Each test case consists of two lines. The fi rst contains the number n (1<=n<=10⁶), the number of integers in the sequence. The second contains n integers a₀,..., a_n-1 (-1000<=a_i<=1000) representing the sequence of numbers. The input will finish with a line containing 0.

Output

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.

Sample Input

3

2 2 1

3

-1 1 1 

1

-1

0

Sample Output

3

2

0

Source

SWERC 2011

Recommend

lcy | We have carefully selected several similar problems for you: 4190 4192 4187 4188 4189

 1 /*
 2 题意：
 3 刚刚又一道hdu的题目；
 4 题意：10^6个数字，有10^6种形式。
 5 如  a b c d ,  b c d a ,  c d a b,  d a b c;
 6 统计在所以情况中如果满足任意前i数和都>=0 的个数。
 7 想了一下，思路有了。可以这样子。
 8 任意前i数和都满足>=0，那么最小的是不是也就满足了呢?
 9 肯定的。所以。题目可以转换为
10 以i为开头，长度为n的前提下，求最小值。
11 这样的话，只有q[head].sum - s[ i - n];
12 
13  */
14 
15 #include<iostream>
16 #include<stdio.h>
17 #include<cstring>
18 #include<cstdlib>
19 using namespace std;
20 
21 int a[1000002];
22 int s[2000002];
23 typedef struct
24 {
25     int num;
26     int sum;
27 }Queue;
28 Queue tmp,q[2000004];
29 
30 int main()
31 {
32     int n,i,len,Num,tom;
33     int head,tail;
34     while(scanf("%d",&n)>0)
35     {
36         if(n==0)break;
37         for(i=1;i<=n;i++)
38             scanf("%d",&a[i]);
39             len=n*2;
40         for(i=n+1;i<=len;i++)
41             a[i]=a[i-n];
42         for(s[0]=0,i=1;i<=len;i++)
43             s[i]=s[i-1]+a[i];
44         head=0;tail= -1; Num=1; tom=0;
45         for(i=1;i<=len;i++)
46         {
47             tmp.num=++Num;
48             tmp.sum=s[i];
49             while( head<=tail && q[tail].sum>tmp.sum ) tail --;
50             q[++tail]=tmp;
51             if( i>n )
52             {
53                 while( head<=tail && q[head].num+n<=i ) head++;
54                 if( q[head].sum-s[i-n]>=0) tom++;
55             }
56         }
57         printf("%d
",tom);
58     }
59     return 0;
60 }