d563. 等值首尾和 - 高中生程式解題系統

d563. 等值首尾和

標籤 : 陣列
通過比率 : 1390人/1680人 ( 83% ) [非即時]
評分方式：

Tolerant

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

內容

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

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

輸入說明

每個測資檔只有一組測資，共兩行。
第一行整數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 (全部陣列的和，也代表答案至少有一組)

輸出說明

等值首尾和的數目

範例輸入 #1

7
3 6 2 1 4 5 2

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (50%): 1.0s , <1K
公開測資點#1 (50%): 1.0s , <1M

提示：

共計兩個測資點。

第一個測資點n=20

第二個測資點n=100000

標籤:

陣列

出處:

名題精選百則 [管理者： jack1 (我是韜哥我忘了拿通知單) ]

本題狀況本題討論排行