---
# System prepended metadata

title: '題解 zerojudge f581: 3. 圓環出口'
tags: [zerojudge, 二分搜尋法（Binary Search）, APCS, 題解, lower_bound]

---

###### tags: `APCS` `二分搜尋法（Binary Search）` `lower_bound` `zerojudge` `題解`
# 題解 zerojudge f581: 3. 圓環出口
## STL lower_bound/二分搜尋法（Binary Search）
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<long long>P;
int main(){
    int n,m,k;
    cin>>n>>m;
    long long total=0;
    for(int i=0;i<n;i++){
        cin>>k;
        total+=k;
        P.push_back(total);
    }
    long long Q;
    int idx=0;
    for(int i=0;i<m;i++){
        cin>>Q;
        if(idx!=0)  Q+=P[idx-1];
        while(Q>total)  Q-=total;
        idx=lower_bound(P.begin(),P.end(),Q)-P.begin()+1;
        idx%=n;
    }
    cout<<idx;
}
```