# 演算法題 - 圓環出口 - APCS - by Peter Wang
## 題目資訊
此題為2020.7 測驗中的題目3
###### tags: `APCS` lower bound`

## 題目敘述
有 n 個房間排成一個環，編號分別是 0 到 n−1。

房間之間有單向的路徑，編號 i 的房間可以走到編號 (i+1)modn的房間。

每次進入編號 i 的房間可以獲得 pi 個點數（最一開始待的房間也可以獲得點數）。

現在依序有 m 個任務，第 i 個任務需要蒐集到 qi 個點數。對於每次的任務，若一開始在編號 s 的房間，且走到編號 t 的房間時候可以蒐集到需要的點數，則完成這次任務後會停在編號 (t+1)modn 的房間。

一開始在編號 0 的房間，依據接收到 m 個任務，請求出完成第 m 個任務後會停在哪個編號的房間？
### 輸入：
第一行包含兩個正整數 n,m(1≤n≤200000,1≤m≤20000)。

第二行包含 n 個正整數 p0,p1,p2,…,pn−1，p 的總和不超過 109。

第三行包含 m 個正整數 q0,q1,q2,…,qm−1，qi 不會超過 p 的總和。
### 輸出：
輸出一個非負整數表示最後停在哪個編號的房間

## 解題思路
利用vector內建功能lower bound找出前綴，並算出位置，就能得到答案。

## 程式碼

#include <iostream>
#include <vector>
using namespace std;
 
int n, m, p[200005];
vector <int> pre;
 
int main() {
    cin >> n >> m;
    for (int i = 0, tot = 0; i < n; i++){
        cin >> p[i];
        tot += p[i];
        pre.push_back(tot);
    }
    int s = 0;
    for (int i = 0, q; i < m; i++){
        cin >> q;
        if (s != 0) q += pre[s-1];
        if (q > pre[n-1]) q -= pre[n-1];
        s = (int)(lower_bound(pre.begin(), pre.end(), q)-pre.begin())+1;
        s %= n;
    }
    cout << s << endl;
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=f581)

## 備註
>[name=PeterWang]
>[time=Sat, Aug 7, 2021 9:25 PM]