https://codeforces.com/contest/1933/problem/E
题目大意
给出 $n$ 长的数组 $a$。
对于某个 $u$，如果连续训练 $k$ 次则获得收益为，后面的收益可以为负。
$u + (u - 1) + (u - 2) + \cdots + (u + 1 - k)$。
给出 $q$ 个询问，每次询问给出 $l$ 和 $u$。问最佳的 $r >= l$ 使得 $\sum_{i = l}^{r} a[i]$ 次训练的收益最大，当有多个 $r$ 满足条件时选较小的。
$1 \le n, q \le 10^5$。$1 \le a_i \le 10^4$。$1 \le l \le n$。$1 \le u \le 10^9$。
简要题解
显然当进行 $u + 1$ 次时收益为 $0$，超过 $u + 1$ 次收益开始下降，因此我们只要二分最接近这里的值即可。可以用前缀和辅助一下这个操作。
细节上 $u$ 次总是最好的，否则 $u + 1$ -> $u - 1$ -> $u + 2$ -> $u - 2$ -> $\cdots$。
复杂度
$T$：$O(n \log u)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<int> sum{0};
for (int i : a) sum.push_back(sum.back() + i);
int q; cin >> q;
int l, u;
for (int ii = 0; ii < q; ii++) {
cin >> l >> u;
int tar = sum[l - 1] + u;
int r = upper_bound(sum.begin(), sum.end(), tar) - sum.begin();
// cerr << l << ' ' << u << ' ' << tar << ' ' << r << endl;
if (r == n + 1) {
r = r - 1;
}
if (r > l && abs(sum[r] - sum[l - 1] - u) > abs(sum[r - 1] - sum[l - 1] - u)) {
r = r - 1;
}
cout << r << (" \n"[ii == q - 1]);
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Cost of the Array - Codeforces Round 1002 (Div. 2)