f581ac - Error
題目描述
題目要求模擬一個環狀陣列的查詢操作。給定一個包含 n 個正整數的陣列 a，以及 m 個查詢。對於每個查詢 target，找到陣列中累積和（prefix sum）大於等於 target 的第一個位置的索引，並將該索引作為下一個查詢的起始位置。
解題思路
本題的核心思想是利用前綴和和二分搜尋來高效地找到滿足條件的位置。首先，計算陣列 a 的前綴和 S。然後，對於每個查詢 target，從當前位置 pos 開始，計算從 pos 出發的累積和。使用二分搜尋在 S 陣列中找到第一個大於等於 target + S[pos] - a[pos] 的位置。找到該位置後，將其轉換為環狀陣列中的索引，並作為下一個查詢的起始位置。
複雜度分析
- 時間複雜度: O(n + m * log n)
- 空間複雜度: O(n)
程式碼
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long sum = 0;
vector<long long> a, S;
void init() {
cin >> n >> m;
assert(1 <= n && n <= 200000);
assert(1 <= m && m <= 20000);
a.resize(2 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
assert(1 <= a[i]);
sum += a[i];
a[i + n] = a[i];
}
assert(sum <= 1000000000ll);
S.resize(2 * n);
long long psum = 0;
for (int i = 0; i < 2 * n; i++) {
psum += a[i];
S[i] = psum;
}
}
int next_pos(int pos, long long target) {
target += S[pos] - a[pos];
int L = pos;
int R = pos + n;
pos = lower_bound(S.begin() + L, S.begin() + R, target) - S.begin();
return (pos + 1) % n;
}
int main() {
init();
int pos = 0;
for (int cs = 1; cs <= m; cs++) {
int target;
cin >> target;
assert(1 <= target && target <= sum);
cout << pos << "\n";
pos = next_pos(pos, target);
}
cout << pos << endl;
}