T1：加下标
最小值最大 \(\to\) 二分答案
最小值等于 \(m\) 可转化为所有数 \(\geqslant m\)
二分 \(m\)，找到满足 \(k\) 次操作后，可使所有数都 \(\geqslant m\) 的最大的 \(m\)
$check(m)$ 中就判断：能否在 \(k\) 次操作内使所有数都 \(\geqslant m\)，找到使得 \(check(m)\) 为 true 的最大 \(m\) 即为答案
\(check\) 可转化为判断如果要让所有数都 \(\geqslant m\)，需要的操作次数是否 \(\leqslant k\)
用贪心法求操作次数
对每个 \(a_i'\) 增加若干个 \(i\) 使其 \(\geqslant m\)
每次 \(check\) 都是对原始 \(a\) 加下标，所有每次要用一个新数组复制 \(a\) 再增加
可以开一个变量 sum 来记录对每个下标进行操作的增量，这样就能减少一重循环
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<ll> a(n);
rep(i, n) cin >> a[i];
ll ac = 0, wa = 1e18;
while (abs(ac-wa) > 1) {
ll wj = (ac+wa)/2;
auto ok = [&]{
ll cnt = 0, sum = 0;
rep(i, n) if (a[i]+sum < wj) {
ll t = (wj-a[i]-sum+i)/(i+1);
cnt += t;
sum += t*(i+1);
}
return cnt <= k;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}