Funny Positive Sequence 找正序列

zxj015

<div id="cnblogs_post_body">http://acm.fzu.edu.cn/problem.php?pid=1914
题目大意是序列A(a1,a2,a3......an),序列B(b1,b2,b3......bn)，且序列B由序列A生成(bi=a1+a2,+…+ai (1≤i≤n))，若序列B内元素都为正数，则称序列A为一个正序列。
现在左移序列A内的元素0,1,2.....n-1次，产生n个新的序列：
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
问{ A(0), A(1), …, A(n-2), A(n-1) }内有多少个正序列。
总体思想是先找到一个<=0的数ai，然后向前加(ai+ai-1)，若小于等于0说明该元素(ai-1)不可能放在序列首（因为已经不满足和为正数的要求）
这样向前循环遍历一遍序列就可找出所有不可放在序列首的元素。剩下的元素即是正序列的个数。
<div class="cnblogs_code"> 1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 int p[500001], flag[500001]; 5 int main() 6 { 7     int m , n; 8     int i, index, ans, cas = 0; 9     long long sum;10     scanf("%d", &m);11     while(cas < m)12     {13               index = -1;14               sum = 0;15               memset(flag, 0, sizeof(flag));16               scanf("%d", &n);17               for (i = 0;i < n;i++)18               {19                       scanf("%d", &p);20                       if(p <= 0)21                               index = i;22                       sum += p;23               }24               if (index == -1)25               {//都为正数 ,直接输出n 26                       printf("Case %d: %d\n", ++cas, n);27                       continue;28               }29               if (sum <= 0)30               {//和小于等于0,直接输出0 31                       printf("Case %d: 0\n", ++cas);32                       continue;33               }34               flag[index] = -1;35               sum = p[index];36               for (i = (index - 1 + n)%n; i != index; i = (i - 1 + n)%n)37               {38                     sum += p;39                     if(sum > 0)40                     {41                            sum = 0;42                            continue;43                     }44                     flag = -1;    45               }46               i = index;47               sum += p; 48               while (sum <= 0)49               {50                     flag = -1;51                     i = (i - 1 + n)%n;    52                     sum += p;        53               }  54               ans = 0;55               for (i = 0; i < n; i++)56                     if (flag == 0)57                     ans++;58               printf("Case %d: %d\n", ++cas, ans);59     }60     return 0;61 }