有 $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 。
一開始在編號 0 的房間,依據接收到 $m$ 個任務,請求出完成第 $m$ 個任務後會停在哪個編號的房間?
第一行有兩個正整數n 與m,
第二行有n個正整數,依序是各房間的點數p(i),
第三行有 m 個正整數依序是各鑰匙需要的點數Q(i)。
同一行連續二數字間以空白隔開。n不超過2e5,m不超過2e4,p(i)總和不超過1e9,Q(i)不超過所有p(i)總和。
輸出拿到最後一把鑰匙時所在的房間編號。
7 3 2 1 5 4 3 5 3 8 9 12
4
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |