HDU 1193 Non-negative Partial Sums / 单调队列

时间：2014-02-09 15:24:52 收藏：0 阅读：345

Non-negative Partial Sums

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

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

Sample Output

3
2
0

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1000010;
int a[maxn*2];
int q[maxn*2];
int main()
{
    int n;
    while(scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            a[i+n] = a[i];
        }
        int cnt = 0;
        for(int i = 1; i <= 2*n; i++)
            a[i] += a[i-1];
        int front = 0, rear = -1;
        
        for(int i = 1; i < 2*n; i++)
        {
            while(front <= rear && i - q[front] >= n)
                front++;   
            while(front <= rear && a[i] <= a[q[rear]])
                rear--;
            q[++rear] = i;
            if(i >= n && a[q[front]] - a[i-n] >= 0)
                cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

原文：http://blog.csdn.net/u011686226/article/details/18984465