首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

算是我對於D&C部分的第一次小推導
其實沒有很難，希望在APCS的時候也能如此發揮
不過老實說我一開始並沒有想到用二分搜
是在後來看到(n<=200000)才驚覺一般搜尋估計會TLE

解題想法

我使用Lower_bound搭配前綴和(累加)
還有一個變數代表現在是第幾項(now)
說白了就是把一個陣列模擬包裝的概念罷了
(習慣開long long int 版面醜很抱歉)
Lower_bound的部分是本題我的解題關鍵
只需要二分搜索求元素扣掉當前位置(now)的前一個元素(因為累加，所以可以得到這段區間的和)
至於二分搜的形式有好多種，關鍵觀念不要偏就好
比較需要注意的是可以自己想想看
使用陣列模擬的情況下，回到開頭的各變數修改(小麻煩)

AC code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll int n,m,now=0,p,g;
ll int a[200005],ans=0;
ll int lower_bound(ll int left,ll int right,ll int goal){
    ll int mid,pos,ps=0;
    bool ta=true;
    if(left!=0){
        ps=a[left-1];
    }
    while(left<right){
        mid=(left+right)/2;
        if((a[mid]-ps)==goal){
            pos=mid;
            ta=false;
            break;
        }
        else if((a[mid]-ps)>goal){
            // too right
            right=mid;
            ta=false;
            pos=right;
        }
        else{
            left=mid+1;
            pos=left;
        }
    }
    if(ta){
        return lower_bound(0,right,goal-(a[right-1]-ps));
    }
    else{
        return pos;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int x=0;x<n;x++){
        cin >> a[x];
        ans+=a[x];
        a[x]=ans;
    }
    while(m--){
        cin >> p;
        g=lower_bound(now,n,p);
        now=(g+1)%n;
    }
    cout << now << endl;
    return 0;
}

題目連結 : 2020年7月APCS 3.圓環出口