题解：AT_abc457_d [ABC457D] Raise Minimum

wsy_I · 2026-05-10 10:21:58 · 题解

这一道题要求我们最大化 \min_{1\leq i\leq n} a_i。对于此类最小值最大化的问题，并且直接做并不简单，我们可以考虑二分答案。

上界是什么？注意到这里 a_1\leq 10^{18}，k\leq 10^{18}，所以 a_1 不会超过 2\times 10^{18}，于是就可以得到一个宽松的上界 2\times 10^{18}，但是够用了。

下界显然是 1。判断的时候，只需要枚举每一个数，累加最少需要的次数就可以了。当然，我们需要注意一点：最大的次数可以达到 V\log V，其中 V 为值域，所以可能会爆 long long，我吃了一发罚时。不开 __int128 的一中方法是假如当前累加到的次数已经大于 k 了，那么就肯定不合法，跳出。下面是代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 5;
int L = 1, R = 2e18, n, a[N], k, ans;

bool check(int x) {
    int res = 0;
    for(int i = 1; i <= n; i ++ ) {
        if(a[i] < x) res += (x - a[i] + i - 1) / i;
        if(res > k) return false;
    }
    return true;
}

signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    while(L <= R) {
        int mid = L + R >> 1;
        if(check(mid)) ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    cout << ans << endl;
    return 0;
}