C. To Become Max

原题链接

题解

显然采用二分答案，下面讲解 check 函数怎么写。

观察到 n 的属于1000以内，所以我们的check函数可以采用平方的复杂度。

我们采取枚举法，假定 ai 可以达到我们的理想值，那么我们只需要从 i 位置开始考虑 k 怎么分配即可。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[1005];
int n,k;

bool check(int to_){
    
    for (int i=1;i<=n-1;i++){
        int cnt=k,j=i,m=to_;
        
        for (;j<=n-1;j++){
            if (a[j]>=m) break;
            else cnt-=m-a[j];
            if (cnt<0) break;
            m--;
        }
        
        if ((a[n]>=m || a[j]>=m) && cnt>=0) return true;
    }
    
    return false;
}

void solve(){
    cin>>n>>k;
    
    int l=0,r=0;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        l=max(l,a[i]);
    }
    r=l+k+1;
    
    while (l+1<r){
        int mid=(l+r)>>1;
        if (check(mid)) l=mid;
        else r=mid;
    }
    
    cout<<l<<endl;
}

int main(){
    //freopen("input.txt","r",stdin);
    int t;
    cin>>t;
    while (t--){
        solve();
    }
    return 0;
}