2015
05-23

# Non-negative Partial Sums

You are given a sequence of n numbers a0,…, an-1. A cyclic shift by k positions (0<=k<=n-1) results in the following sequence: ak ak+1,…, an-1, a0, a1,…, ak-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?

Each test case consists of two lines. The fi rst contains the number n (1<=n<=106), the number of integers in the sequence. The second contains n integers a0,…, an-1 (-1000<=ai<=1000) representing the sequence of numbers. The input will finish with a line containing 0.

Each test case consists of two lines. The fi rst contains the number n (1<=n<=106), the number of integers in the sequence. The second contains n integers a0,…, an-1 (-1000<=ai<=1000) representing the sequence of numbers. The input will finish with a line containing 0.

3
2 2 1
3
-1 1 1
1
-1
0

3
2
0

/*

数据结构的分析类问题。
觉得是道挺有意思的水题，本来没想发，不过随便搜了下后发现清一色的单调队列。。

这里说的移动，都是将最后一个元素放到首位。
1.如果sum<0，那么坑定ans=0；
2.很容易发现一个性质，如果当前的长度为n的序列满足题中的那个条件，那么我们可以

如果这个元素>=0，那么这次移动得到的新队列同样满足题中的条件；
如果这个元素<0，那么可以设置一个量来累加这个值，直到某次移动移动后这个累计

再详细的看代码吧，很短。至于单调队列？啥东西囧～？估计也就我这种非计算机专业

2013-07-31
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=1000006;

int n,num[N],ans;
int main()
{
int i,l;
int p,acc,sum,cnt;
while(scanf("%d",&n),n)
{
sum=0;
for(i=0;i<n;i++){scanf("%d",&num[i]);sum+=num[i];}
if(sum<0)    {printf("0\n");continue;}

p=n-1;
ans=cnt=sum=0;
while(cnt<=p)
{
sum+=num[cnt++];
while(sum<0)    sum+=num[p--];
}
acc=0;
while(p>=0)
{
if(acc>=0)        ans++;
if(acc<0)        acc+=num[p];
else if(num[p]<0)    acc=num[p];
p--;
}
printf("%d\n",ans);
}
return 0;
}