Non-negative Partial Sums

You are given a sequence of n numbers a₀,..., a_n-1. A cyclic shift by k positions ( 0kn - 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 first i numbers is greater than or equal to zero for all i with 1in?

Input 

Each test case consists of two lines. The first contains the number n ( 1n10⁶), the number of integers in the sequence. The second contains n integers a₀,..., a_n-1 ( -1000a_i1000) 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

---

先將 A[] 複製一段，將環狀展開。
如果將其數列改成 S[i] = sigma(A[k]) (1<= k <= i),
那麼要符合所需要的規定，代表固定區間長度 S[i, i+n-1] 的最小值 要大於等於 S[i]。

使用單調隊列去維護他的調查。

因此做一個嚴格遞增的單調隊列，不懂單調隊列可以上網查一下，通常用在 動態規劃 中。

#include <stdio.h>
#define maxN 1048576<<1
int S[maxN], Q[maxN];
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    // using monotone queue (increasing)
    int n, x, i, j;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
            ReadInt(&x);
            S[i+n] = S[i] = x;
        }
        int n2 = n<<1;
        for(i = 1; i < n2; i++)
            S[i] += S[i-1];
        int head = 0, tail = 0, ans = 0;
        for(i = 0; i < n2; i++) {
            while(head < tail && S[Q[tail-1]] >= S[i])
                tail--;
            Q[tail++] = i;
            if(i >= n && S[Q[head]] >= S[i-n])
                ans++;
            while(head < tail && Q[head] <= i-n)
                head++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

---