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
}
?
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
