题解：AT_abc457_d [ABC457D] Raise Minimum

liangliang517 · 2026-05-10 09:18:58 · 题解

思路

显然，我们可以考虑二分答案。因为 A_1 最多只能加到 2 \times 10^{18}，所以答案最多只可能达到 2 \times 10^{18}。接下来当我们二分到 z 时，我们记录一个变量 sum = \sum_{i = 1}^{N} \max \left ( 0,\left \lfloor \frac{z - a_i - 1}{i} \right \rfloor + 1 \right ) 表示使得 \min_{1 \le i \le n}A_i \ge z 所需的最小操作次数。当 sum \le K 时则表示 \min_{1 \le i \le n}A_i 可以达到 z。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,l=1,r=2e18,z,sum,a[200010];
int main(  ){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    while(l<=r){
        z=(l+r)/2,sum=0;
        for(long long i=1;i<=n;i++){
            if(a[i]>=z) continue;
            sum=sum+max(0ll,(z-a[i]-1)/i+1);
            if(sum>m) break;
        }
        if(sum<=m) l=z+1;
        else r=z-1;
    }
    cout<<l-1<<endl;
    return 0;
}