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)
