發表新討論
#16346: 提供一些想法


giant0620 (BlenderWang)

學校 : 國立彰化師範大學
編號 : 61100
來源 : [140.113.207.98]
最後登入時間 ：
2022-07-25 14:26:46
d563. 等值首尾和 -- 名題精選百則 | From: [118.163.203.105] | 發表日期 : 2018-12-21 12:52

題目規定陣列中每一項都是正整數，所以可以另外製作一個陣列，裡面存放從0 到 n-1項的前段和，這樣這個陣列會是一個嚴格遞增數列

這個陣列就能使用二分搜尋法來查找後段和有沒有一樣了，速度會快很多

程式的核心概念(這不是實際程式碼喔，只是個概念)會像這樣:

for(i = 0  ->  n-1)

   讀入數字到arr1

sum = 0,count = 0

for(i = 0  ->  n-1)

   sum = sum + arr1[i] //前段和

   arr2[i] = sum 

sum = 0

for(i = n-1  ->  0)

   sum = sum + arr1[i]  //後段和

   if(binary_search(sum , arr2 , n) == 1)

      count++;

 
#16924: Re:提供一些想法


chuck2000 (chuck2000)

學校 : 國立彰化師範大學
編號 : 87955
來源 : [120.107.188.22]
最後登入時間 ：
2022-03-21 17:59:40
d563. 等值首尾和 -- 名題精選百則 | From: [118.163.203.106] | 發表日期 : 2019-02-21 22:58

題目規定陣列中每一項都是正整數，所以可以另外製作一個陣列，裡面存放從0 到 n-1項的前段和，這樣這個陣列會是一個嚴格遞增數列

這個陣列就能使用二分搜尋法來查找後段和有沒有一樣了，速度會快很多

程式的核心概念(這不是實際程式碼喔，只是個概念)會像這樣:

for(i = 0  ->  n-1)

   讀入數字到arr1

sum = 0,count = 0

for(i = 0  ->  n-1)

   sum = sum + arr1[i] //前段和

   arr2[i] = sum 

sum = 0

for(i = n-1  ->  0)

   sum = sum + arr1[i]  //後段和

   if(binary_search(sum , arr2 , n) == 1)

      count++;

感謝提供想法!已AC!!!


 
ZeroJudge Forum