题解：AT_abc457_d [ABC457D] Raise Minimum

LBXJLXR · 2026-05-10 11:16:15 · 题解

前言

赛时有二分答案的思路，但是 check 写炸了，赛时真唐。后来一看，卧槽原来这么简单！必须写篇题解弥补一下。

题目大意

给定 n 个数，你可以进行 0 次，1 次，…，K 次的以下操作：\ 选择一个数 A_i，并将 A_i 加上 i。\ 最后输出这个数列中最小的数最大能是多少？（进行最优操作后）

思路

在遇到这样像求最小值最大呀，最大值最小之类的问题，我们便可以使用二分答案的思路，在这题中，check 可以只用贪心的思路。贴个代码（下文 ll 指 long long）。

bool check(ll mid){
    ll ct=0;
    for(int i=1;i<=n;++i){
        if(a[i]<mid){
            ct+=(mid-a[i]+i-1)/i; // 至少加多少次才能达到 mid 
            if(ct>k) return false; //一旦超出，直接返回失败 
        }
    }
    return ct<=k;
}

这样一来，其他最很好写了，至于二分的右边界，我们就将它设为 a[1]+k+1，最大可能就是将 k 次操作都加在 a_1 上，也就是 a[1]+k，加 1 就是因为二分区间是左闭右开的。

如果实在看不懂的话，就设为一个很大的值吧，应该也能过。

AC code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
ll a[MAXN];
ll n,k;

bool check(ll mid){
    ll ct=0;
    for(int i=1;i<=n;++i){
        if(a[i]<mid){
            ct+=(mid-a[i]+i-1)/i; // 至少加多少次才能达到 mid 
            if(ct>k) return false; //一旦超出，直接返回失败 
        }
    }
    return ct<=k;
}

ll solve(ll l,ll r){
    ll left=l,right=r;
    while(left<right){
        ll mid=left+((right-left)>>1);
        if(check(mid)){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left-1;
}

int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    ll ans=solve(1,a[1]+k+1);
    printf("%lld",ans);
    return 0;
}

制作不易，祝所有点赞的同学们 AK 每一场比赛！谢谢啦！