a166: P-2-15. 圓環出口
標籤 : APCS202007
通過比率 : 11人/12人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-02 16:31

內容

有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不超過2e5,m不超過2e4,p(i)總和不超過1e9,Q(i)不超過所有p(i)總和

輸出說明

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

範例輸入 #1
7 3
2 1 5 4 3 5 3
8 9 12
範例輸出 #1
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
提示 :

每次要在一個正整數陣列中,對於某個開始位置,找到一個最小的區間,滿足區間和大於等於某輸入Q(i)。關於圓環,有兩個簡單的處理方式,一個是判斷超過結尾時,從頭開始;另外一種方式是將陣列重複兩次,每次找到後除以n取餘數。最簡單的搜尋方法就是一個一個往下找,程式也很好寫,但是效率不夠好

標籤:
APCS202007
出處:
AP325 [管理者: ]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」