f581 - 3. 圓環出口
題目描述
題目描述一個環狀的房間，每個房間都有一定的點數。給定 $n$ 個房間的點數和 $m$ 個任務，每個任務需要蒐集到 $q_i$ 個點數。從房間 $0$ 開始，每次完成任務後會停在下一個房間。要求完成所有任務後停在哪個房間。
解題思路
本題的核心在於高效地計算在環上移動到蒐集到指定點數時所在的房間。
- 前綴和: 首先計算每個房間的前綴和
dp[i]，表示從房間 0 到房間 i 的總點數。 - 模運算: 因為房間是環狀的，所以需要使用模運算來處理超出房間數的情況。
- 二分搜尋: 對於每個任務，使用二分搜尋在
dp陣列中找到第一個大於或等於任務所需點數t的房間。 - 更新位置: 找到房間後，更新當前位置為下一個房間
(lower_bound(dp,dp+n,t)-dp+1)%n。
複雜度分析
- 時間複雜度: O(m * log n)，其中 m 是任務數量，n 是房間數量。二分搜尋的複雜度為 O(log n)，需要執行 m 次。
- 空間複雜度: O(n)，用於儲存前綴和
dp陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long int a[200001],dp[200001],n,m,ans,t,sum;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> a[i];
if(i)
dp[i]=a[i]+dp[i-1];
else
dp[i]=a[i];
//cout << dp[i] << " ";
}
sum=dp[n-1];
//cout << "\n";
for(int i=0;i<m;++i){
cin >> t;
//cout << t << " ";
t+=dp[ans]-a[ans];
t%=sum;
//cout << t << " ";
if(t==0)
ans=0;
else
ans=(lower_bound(dp,dp+n,t)-dp+1)%n;
//cout << ans << '\n';
}
cout << ans ;
}