有 $ 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$ 。
第一行有兩個正整數 $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)} $。
輸出拿到最後一把鑰匙時所在的房間編號
7 3 2 1 5 4 3 5 3 8 9 12
4
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||