d563: 等值首尾和
Tags : 陣列
Accepted rate : 1121人/1360人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-12-18 11:29

Content

假設有一個陣列x[],它有n個元素,每一個都大於零;我們說x[0]+x[1]+...+x[i]是個前段和(Prefix Sum),而x[j]+x[j+1]+...+x[n-1]則是個後段和(Suffix Sum)。請寫一個程式,求出x[]中有多少組相同的前段和與後段和。

(上述文字、題目來自名題精選百則 - 冼鏡光著 - 儒林出版)

Input

 每個測資檔只有一組測資,共兩行。
 第一行整數n(1<=n<=100000)代表數列有幾個數字
 第二行有n個正整數(A1,A2,...,An),並且全部總合小於2147483647,以空格隔開

--

範例測資3,6,2,1,4,5,2有三組等值首尾和,分別是:

11 = 3+6+2 = 2+5+4

12 = 3+6+2+1 = 2+5+4+1

23 = 3+6+2+1+4+5+2 = 2+5+4+1+2+6+3 (全部陣列的和,也代表答案至少有一組)

Output
等值首尾和的數目
Sample Input #1
7
3 6 2 1 4 5 2
Sample Output #1
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1M
Hint :

共計兩個測資點。

第一個測資點n=20

第二個測資點n=100000

Tags:
陣列
出處:
名題精選百則 [管理者: jack1(我是韜哥我忘了拿通知單) ]


ID User Problem Subject Hit Post Date
28596 sun9410674(11111) d563
沒事
278 2021-12-20 20:41
25188 asnewchien@g...(david) d563
483 2021-04-26 21:37
16346 giant0620(BlenderWang) d563
提供一些想法
1502 2018-12-21 12:52
15700 Python_in_on...(挑戰Python一行AC 不使...) d563
1332 2018-10-21 17:10
13424 mirkat.ee06@...(炭烤海苔) d563
解題想法
1738 2018-02-17 12:52