There are n integers a 1,a 2,…,a n-1,a n in the sequence A, the sum of these n integers is larger than zero. There are n integers b 1,b 2,…,b n-1,b n in the sequence B, B is the generating sequence of A and bi = a 1+a 2,+…+a i (1≤i≤n). If the elements of B are all positive, A is called as a positive sequence.
We left shift the sequence A 0,1,2,…,n-1 times, and get n sequences, that is showed as follows:
A(0): a1,a2,…,an-1,an
A(1): a2,a3,…,an,a1
…
A(n-2): an-1,an,…,an-3,an-2
A(n-1): an,a1,…,an-2,an-1
Your task is to find out the number of positive sequences in the set { A(0), A(1), …, A(n-2), A(n-1) }.
Input
The first line of the input contains an integer T (T <= 20), indicating the number of cases. Each case begins with a line containing one integer n (1 <= n <= 500,000), the number of elements in the sequence. The next line contains n integers ai(-2,000,000,000≤ai≤2,000,000,000,1≤i≤n), the value of elements in the sequence.
Output
For each test case, print a line containing the test case number (beginning with 1) and the number of positive sequences.
Sample Input
2 3 1 1 -1 8 1 1 1 -1 1 1 1 -1
Sample Output
Case 1: 1 Case 2: 4
思路：可以建立一个长度为2*n的数组，每次查询它的前ai项之和是不是负数，如果是负数，
用vis标记，可以保证后面扫的时候，扫到这个地方就可以停下了
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<set> #include<map> #include<vector> #include<cmath> const int maxn=5e5+5; typedef long long ll; using namespace std; ll a[2*maxn]; int vis[maxn]; int main() { int t,cnt=1,i,n,j; scanf("%d",&t); while(t--) { memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%I64d",&a[i]); a[i+n]=a[i]; } for(i=2*n-1;i>=n;i--) { if(i<n) break; if(a[i]<=0) { ll sum=0; for(j=i;j>i-n;j--) { sum+=a[j]; if(sum<=0) { if(j<n) vis[j]=1; else vis[j-n]=1; } else break; } i=j; } if(i<n) break; } int ans=0; for(i=0;i<n;i++) { if(vis[i]==1) ans++; } printf("Case %d: %d ",cnt++,n-ans); } return 0; }