题解：AT_abc457_d [ABC457D] Raise Minimum

· · 题解

题目十分简单，求经过一系列操作后的 \displaystyle \min_{1 \le i \le N} A_i ，很显然，这是一个二分，我们先对记录每一个 A_i 的 id，然后对序列 A 进行排序，接着二分枚举每一个 \displaystyle \min_{1 \le i \le N} A_i 的可能值，检查所枚举的值是否可行。

::::info[code]

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define rg register
#define PII pair<int,int>
const int N=2e5+5;
int n,k,l=1,r=1e19,ans;
struct node{
    int val,id;
}a[N];
bool cmp(node x,node y){
    return x.val<y.val;
}
bool check(int minn){
    long long cnt=k;
    for(int i=1;i<=n;i++){
        if(a[i].val<minn)
            cnt-=(minn-a[i].val+a[i].id-1)/a[i].id;
        //若a[i]当前值小于最小值，使其加至大于最小值，操作次数ceil(minn-a[i].val)/a[i].id
        else
            break;
        //由于a按val值升序排序，若a[i].val大于minn，则后面都大于minn
        if(cnt<0)
            return 0;
    }
    return cnt>=0;
}
void init();
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].val,a[i].id=i;
    sort(a+1,a+n+1,cmp);
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else
            r=mid-1;
    }
    cout<<ans;
    return 0;
}

::::