C++ APCS 實作題 2020/7 3 : 圓環出口

計算前綴和以及二分搜,以下為程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;

    int q,pSum[200010];
    cin>>pSum[0];
    for(int i=1;i<n;i++){
        cin>>pSum[i];
        pSum[i]=pSum[i]+pSum[i-1];
    }
    int pos=0;
    for(int i=0;i<m;i++){
        cin>>q;
        if(pos!=0){
            if(q>(pSum[n-1]-pSum[pos-1])){
                q-=(pSum[n-1]-pSum[pos-1]);
                q%=pSum[n-1];
                pos=lower_bound(pSum,pSum+n,q)-pSum+1;
            }else{
                pos=lower_bound(pSum,pSum+n,q+pSum[pos-1])-pSum+1;
            }
        }else{
            q%=pSum[n-1];
            pos=lower_bound(pSum,pSum+n,q)-pSum+1;
        }
        pos%=n;
        //cout<<pos<<" ";
    }
    cout<<pos;
    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *