题解：AT_abc457_d [ABC457D] Raise Minimum

FHY_patrickpp · 2026-05-10 12:49:27 · 题解

一眼二分。

二分最终的最小值 x，判断能否在 K 次操作内使得所有 A_i \ge x。

对于某个 A_i，如果当前 A_i \ge x，则不需要操作。

如果 A_i < x，则需要通过若干次操作将其提升到至少 x。每次操作给 A_i 增加 i。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,k,a[N];
bool ck(int x){
    int s=0;
    for(int i=1;i<=n;++i){
        if(a[i]<x){
            int nd=(x-a[i]+i-1)/i;
            s+=nd;
            if(s>k)return 0;
        }
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    int l=0,r=2e18,ans=0;
    while(l<=r){
        int m=l+(r-l)/2;
        if(ck(m))ans=m,l=m+1;
        else r=m-1;
    }
    cout<<ans<<'\n';
}