2020/7/4 圓環出口

2023.1.11 PM 04:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=f581
出題者 : 2020年7月APCS
標籤 : 前綴和、二分搜尋法
難易度 : 3

解題想法 : 
這題可以理解成，做i次任務，每次從目前的位置s往右走並累加pi(包括目前位置的值)，直到走到某個點t，累積的值大於等於qi時，就結束此次任務，並從t+1 (mod n)開始做下一次的任務。

由於累加會越來越大，所以可以使用二分搜尋，快速找到使累加剛好大於等於qi的點，而累加的值就是p陣列 s~t 的區間和。

如果區間和使用線性計算的話，會超出時間限制，因此我們可以利用前綴和快速地算出一段區間的區間和。

假如a[] = {X,1,3,5,2,6,8,3,2}
則a的前綴和陣列pre[] = {0,1,4,9,11,17,25,28,30}
為了方便計算區間和，會在pre[]最前面加上一個0，並把a陣列改為1-base(由index=1處開始存資料)。

如此一來，s~t的區間和就會是pre[t]-pre[s-1]。
    i  0  1  2  3  4  5  6  7  8
  p[i] X  1  3  5  2  6  8  3  2 
pre[i] 0  1  4  9 11 17 25 28 30
sum(p[2]~p[8]) = 3 + 5 + 2 + 6 + 8 + 3 + 2 = pre[8]-pre[2-1] = 29

題解的程式碼中，pre[]的定義和上述有些不同，但相信經過熟悉了前綴和與區間和的關係後，很快就能夠觸類旁通。

//C++ language

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m; cin>>n>>m;
    vector<int>p(n*2),q(m);
    for(int i=0;i<n;i++){
        int x; cin>>x;
        p[i]=p[i+n]=x;
    }
    for(int& i: q) cin>>i;
    vector<int>pre;
    pre.push_back(0);
    for(int i=1;i<=n*2;i++) pre.push_back(pre[i-1]+p[i-1]);
    auto interval_sum = [=](int L,int R){return pre[R+1]-pre[L];};
    int now=0;
    for(int i: q){
        int L=-1,R=n;
        while(R-L>1){
            int m=(L+R)/2;
            if(interval_sum(now,now+m) >= i) R=m;
            else L=m;
        }
        now+=(R+1);
        if(now>=n) now-=n;
    }
    cout<<now<<"\n";
    return 0;
}

## Python language

n,m=map(int,input().split())
p=[int(x) for x in input().split()]
q=[int(x) for x in input().split()]
p+=p
prefix_sum=[0]*(n*2+1)
for i in range(1,n*2+1): prefix_sum[i]=prefix_sum[i-1]+p[i-1]
def interval_sum(L,R): return prefix_sum[R+1]-prefix_sum[L]
now=0
for i in q:
    L=-1; R=n
    while R-L>1:
        m=(L+R)//2
        if interval_sum(now,now+m)>=i: R=m
        else: L=m
    now+=(R+1)
    if now>=n: now-=n
print(now)

相關文章

分享此文：