# f581. 3. 圓環出口
##### link: https://zerojudge.tw/ShowProblem?problemid=f581
###### tags: `binary search` `prefix_sum` `APCS`
這題可以理解成，做 $i$ 次任務，每次從目前的位置$s$往右走並累加 $pi$ (包括目前位置的值)，直到走到某個點 $t$ ，累積的值大於等於 $qi$ 時，就結束此次任務，並從 $t+1$ 開始繼續走。
* 如果一個一個慢慢找，會 TLE
* 思維切入點：由於題目要求的是累加分數，我們可以用**前綴和 + 二分搜**來解決
* 由於每個元素皆為正，累加一定會愈來愈大，因此可以用**左側邊界的二分搜**來搜尋剛好可以完成任務的格子。如果搜尋到最後一個元素還是無法完成任務，則將起點設為零 ( $cur = 0$ ) 然後繼續搜尋。

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int n,m;
int t;
int cur=0, ini = 0;
int c_point=0;

// 左側邊界的二分搜
int search(vector<int> &pre_sum){
    int left=cur,right=pre_sum.size()-1;
    int mid;
    while (right>=left){
        mid=left+(right-left)/2;
        if (pre_sum[mid]-pre_sum[cur]+c_point<t) left=mid+1;
        else if (pre_sum[mid]-pre_sum[cur]+c_point>=t) right=mid-1;
    }
    if (left>pre_sum.size()-1) return pre_sum.size()-1;
    return left;
}

int main(){
    scanf("%d%d",&n,&m);
    vector<int> circle(n),pre_sum(n,0); 
    queue<int> task;
    int a;
    
    for (int i=0;i<n;i++){
        scanf("%d",&circle[i]);
        if (i==0) pre_sum[i]=circle[i];
        else pre_sum[i]=pre_sum[i-1]+circle[i];
    }
    
    for (int i=0;i<m;i++) {
        scanf("%d",&a);
        task.push(a);
    }
    
    while(!task.empty()){
         // 起點的分數 ( 因為我計算區間合的方式關係，並不會算到起點的數字，因此在用前綴和算好區間和之後，還要加上這個 c_point )
        c_point = circle[cur];
        t=task.front();
        task.pop();
        cur=search(pre_sum);
        
        // 如果返回的結果還不能滿足條件 ( 點數不足以完成任務 ) 則歸零繼續算
        if (pre_sum[cur] - pre_sum[ini] + c_point<t){
            t-=(pre_sum[cur]-pre_sum[ini]+c_point);
            cur = 0; ini = 0;
            c_point = pre_sum[cur];
            cur = search(pre_sum);
            }
        /*if ((pre_sum[cur]-pre_sum[ini]+c_point - t)>0) c_point=(pre_sum[cur]-pre_sum[ini]+c_point - t);
        else c_point = 0;*/ 
        // 上面這裡的用意是考慮到可能會需要保留上一個剩下分數而寫( 題目沒說 )，經過實測，不管這行有沒有加都可以過
        if (cur==pre_sum.size()-1) {
            cur=0;
            ini = 0;
        }
        else {
            cur++;
            ini = cur;
        }
    }
    if (cur>pre_sum.size()-1) printf("0");
    else printf("%d",cur);
}