http://acm.fzu.edu.cn/problem.php?pid=1914
题目大意是序列A(a1,a2,a3......an),序列B(b1,b2,b3......bn)，且序列B由序列A生成(bi=a 1 +a 2 ,+…+a i (1≤i≤n))，若序列B内元素都为正数，则称序列A为一个正序列。
现在左移序列A内的元素0,1,2.....n-1次，产生n个新的序列：
A(0): a 1 ,a 2 ,…,a n-1 ,a n
A(1): a 2 ,a 3 ,…,a n ,a 1
…
A(n-2): a n-1 ,a n ,…,a n-3 ,a n-2
A(n-1): a n ,a 1 ,…,a n-2 ,a n-1
问{ A(0), A(1), …, A(n-2), A(n-1) }内有多少个正序列。
总体思想是先找到一个<=0的数 a i ，然后向前加( a i +a i-1 )，若小于等于0说明该元素(a i-1 )不可能放在序列首（因为已经不满足和为正数的要求）
这样向前循环遍历一遍序列就可找出所有不可放在序列首的元素。剩下的元素即是正序列的个数。
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[i]);
20
if
(p[i] <=
0
)
21
index =
i;
22
sum +=
p[i];
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[i];
39
if
(sum >
0
)
40
{
41
sum =
0
;
42
continue
;
43
}
44
flag[i] = -
1
;
45
}
46
i =
index;
47
sum +=
p[i];
48
while
(sum <=
0
)
49
{
50
flag[i] = -
1
;
51
i = (i -
1
+ n)%
n;
52
sum +=
p[i];
53
}
54
ans =
0
;
55
for
(i =
0
; i < n; i++
)
56
if
(flag[i] ==
0
)
57
ans++
;
58
printf(
"
Case %d: %d\n
"
, ++
cas, ans);
59
}
60
return
0
;
61
}
