d024: 例題 P-2-15. 圓環出口 (APCS202007)
Tags : binary search prefix sum
Accepted rate : 4人/6人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-09 14:23

Content

有 n 個房間排列成一個圓環,以順時針方向由 0 到 n - 1 編號。玩家只能順時針方向依序通過這些房間。每當離開第 i 號房間進入下一個房間時,即可獲得 p(i)點。玩家必須依序取得 m 把鑰匙,鑰匙編號由 0 至 m-1,兌換編號 i 的鑰匙所需的點數為 Q(i)。一旦玩家手中的點數達到 Q(i)就會自動獲得編號 i 的鑰匙,而且手中所有的點數就會被「全數收回」,接著要再從當下所在的房間出發,重新收集點數兌換下一把鑰匙。遊戲開始時,玩家位於 0 號房。請計算玩家拿到最後一把鑰匙時所在的房間編號。以下是一個例子。有 7 個房間,p(i)依序是(2, 1, 5, 4, 3, 5, 3),其中 0 號房間的點數是 2。假設所需要的鑰匙為 3 把,Q(i) 依序是(8, 9, 12)。從 0 號房 出發,在「離開 2 號房,進入 3 號房」時,獲得恰好 2+1+5 = 8 點,因此在進入 3 號房時玩家兌換到 0 號鑰匙;接著從 3 號房開始繼續累積點數,直到「離開 5 號房, 進入 6 號房」時,手中的點數為 12,於是在進入 6 號房時獲得 1 號鑰匙,手中點數 再次被清空。最後,從 6 號房出發,直到「離開 3 號房,進入 4 號房」時,方可獲得 至少 12 點的點數,來兌換最後一把鑰匙。因此,拿到最後一把鑰匙時所在的房間編號為 4。

Input

第一行有兩個正整數 $n$ 與 $m$,第二行有 $n$ 個正整數,依序是各房間的點數 $p(i)$,第三行有 $m$ 個正整數依序是各鑰匙需要的點數 $Q(i)$。同一行連續二字間以空白隔開。

$n \leq 2*10^5$,

$ m \leq 2*10^4 $,

$ \sum {p(i)} \leq 10^9 $,

$ Q(i) \leq \sum{p(i)} $。

Output

輸出拿到最後一把鑰匙時所在的房間編號。

Sample Input
7 3
2 1 5 4 3 5 3
8 9 12
Sample Output
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 0.5s , <1M
公開 測資點#1 (20%): 0.5s , <1M
公開 測資點#2 (20%): 0.5s , <1M
公開 測資點#3 (20%): 0.5s , <1M
公開 測資點#4 (20%): 0.5s , <10M
Hint :
Tags:
binary search prefix sum
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」