# APCS實作題2020年7月第3題：圓環出口 > 日期：2024年7月9日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f581) ## 題目 ### 問題描述 有 $n$ 個房間排成一個環，編號分別是 $0$ 到 $n-1$。 房間之間有單向的路徑，編號 $i$ 的房間可以走到編號 $(i+1) \% n$ 的房間。 每次進入編號 $i$ 的房間可以獲得 $p_i$ 個點數（最一開始待的房間也可以獲得點數）。 現在依序有 $m$ 個任務，第 $i$ 個任務需要蒐集到 $q_i$ 個點數。對於每次的任務，若一開始在編號 $s$ 的房間，且走到編號 $t$ 的房間時候可以蒐集到需要的點數，則完成這次任務後會停在編號 $(t+1) \% n$ 的房間。 一開始在編號 $0$ 的房間，依據接收到 $m$ 個任務，請求出完成第 $m$ 個任務後會停在哪個編號的房間？ <br /> ### 輸入說明 第一行包含兩個正整數 $n, m ~(1 \leq n \leq 200000,~ 1\leq m \leq 20000)$。 第二行包含 $n$ 個正整數 $p_0, p_1, p_2, \dots, p_{n-1}$，$p$ 的總和不超過 $10^9$。 第三行包含 $m$ 個正整數 $q_0, q_1, q_2, \dots, q_{m-1}$，$q_i$ 不會超過 $p$ 的總和。 配分 - 20分：$1 \leq n, m \leq 100$ - 80分：同原題目限制。 <br /> ### 輸出格式 輸出一個非負整數表示最後停在哪個編號的房間 <br /> ### 範例輸入1 ``` 7 3 2 1 5 4 3 5 3 8 9 12 ``` ### 範例輸出1 ``` 4 ``` ### 範例輸入2 ``` 4 3 1 3 5 7 4 2 2 ``` ### 範例輸出2 ``` 0 ``` <br /> ## Python 程式碼 費時最久約為 0.3 s，使用記憶體最多約為 27.4 MB，通過測試。 ```python= from bisect import bisect_left n, m = map(int, input().split()) # 讀取房間數量n、任務數量m ps = list(map(int, input().split())) # 讀取房間的分數 qs = list(map(int, input().split())) # 讀取任務需要的分數 for i in range(1, n): ps[i] += ps[i-1] # 將 ps 改成分數的前綴和 imax = ps[-1] # 所有房間分數總合 base = 0 # 分數基底，前一次任務結束時進入的房間分數總合 head = 0 # 從 qs 讀取資料的索引值 idx = 0 # 任務結束時房間的索引值 while head < m: # 如果 head 還沒有出界時繼續執行 q = qs[head] # 讀取任務分數 q head += 1 # head 加 1 q += base # 更新 q，加上 base idx = bisect_left(ps, q) # 二分搜尋，從 ps 中找 q 的索引值 if idx == n: # 如果沒有找到 q，代表 q 太大 q -= imax # q 減掉 imax，由於題目限制，q <= 2*imax idx = bisect_left(ps, q) # 再找一次 q base = ps[idx] # 更新 base print((idx+1) % n) # 印出答案 ``` 如果 while 迴圈採用以下的寫法，在第3筆測資會出錯，因為第3行 base + q 如果等於 imax，應該會對應到 ps 最後一項，但是先取 %imax 會變成 0。 ```python= while qs: q = qs.pop(0) q = (base + q) % imax idx = bisect_left(ps, q) base = ps[idx] ``` <br /><br /> ## C++ 程式碼 費時最久約為 0.2 s，使用記憶體最多約為 1.2 MB，通過測試。 ```cpp= #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; // 讀取房間數量n、任務數量m vector<int> ps (n, 0), qs (m, 0); for(int i=0; i<n; i++) cin >> ps[i]; // 讀取房間的分數 for(int i=0; i<m; i++) cin >> qs[i]; // 讀取任務需要的分數 for(int i=1; i<n; i++) ps[i] += ps[i-1]; // 將 ps 改成分數的前綴和 int imax = ps[n-1], base = 0, idx = 0, head = 0, q; while(head < m) { // 如果 head 還沒有出界時繼續執行 q = qs[head]; // 讀取任務分數 q head ++; // head 加 1 q += base; // 更新 q，加上 base idx = lower_bound(ps.begin(), ps.end(), q) - ps.begin(); // 二分搜尋，從 ps 中找 q 的索引值 if (idx == n) { // 如果沒有找到 q，代表 q 太大 q -= imax; // q 減掉 imax，由於題目限制，q <= 2*imax idx = lower_bound(ps.begin(), ps.end(), q) - ps.begin(); // 再找一次 q } base = ps[idx]; // 更新 base } cout << (idx+1) % n << "\n"; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`