創作內容

0 GP

ZeroJudge - e346: 區間和練習 解題心得

作者:Not In My Back Yard│2019-08-07 22:28:17│巴幣:0│人氣:250
題目連結:


題目大意:
給定一正整數 n (1 ≦ n ≦ 200000),代表一數列 A 的長度。接著的一列有 n 個整數(絕對值皆不超過 10 ^ 9),依序代表 A1 、 A2 、 …… 、 An 的值。

再緊接著的一列給定一正整數 q (1 ≦ q ≦ 200000),代表有 q 筆的詢問。每筆詢問佔一列,每列給定兩正整數 l 、 r ,代表詢問 Al ~ Ar 這 r - l + 1 個數字的總和為多少?



範例輸入:
5
1 2 3 4 5
3
1 3
2 4
3 5


範例輸出:
6
9
12


解題思維:
先計算數列 A 的前綴和數列 S(見先前的文章)。設 S0 = 0 、 S1 = A1 、 S2 = A1 + A2 、 …… 、 Sn = A1 + A2 + …… + An ,則每給定一對 l 、 r 值,所求即為 Sr - S(l-1) 。而不用重複地用迴圈去計算 Al ~ Ar 的總和。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4487413
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

rogerjian錢太多的人?
炫富用的表情貼? https://line.me/S/emoji/?id=61ef9927ed42d1764705aa1d看更多我要大聲說昨天19:10


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】