题解十二：P13500 「Cfz Round 6」Kyu-kurarin

· · 题解

题目 | 题解

题意

一个正整数序列 a，进行 s 次操作，每次将 k 个数增加 1，求出最大的 s 使得序列中的每一项满足 a_i-s>0。

思路

本题的答案显然具有单调性。所以，二分答案。

对于一个 s，要判断它是否满足要求，我们就需要对原序列的每一项 a_i 进行判断：如果不满足 a_i-s > 0，就需要增加 a_i 直到满足，并把这个增加量增加到一个变量 num 中。（显然，如果一项本身就满足条件便不需要增加。）最后，num 就记录了使得整个序列满足条件的总增加量。由题意可知，s 次操作最多可以增加 s \times k 次。若满足 num \le s \times k 则 s 符合题意，反之不符合。

bool check(ll s){
    ll num=0;
    for(ll i=1;i<=n;i++){
        num+=max((ll)0,s-a[i]+1);
        if(num>s*k) return false;
    }return true;
}

::::info[s-a[i]+1 的含义] 由 a_i-s > 0 可以得出 a_i > s 时该项满足条件。

反过来，当 a_i \le s 时不满足条件，需要增加。显然把 a_i 增加到 s+1 就可以满足条件。而 s+1 与 a_i 相减的差（即 a_i 的“增加量”）便是 s-a_i+1。（好像是句废话。）

若是该项本身就满足 a_i > s，那么 s-a_i+1 的结果便是非正数。使用 max() 在该式与 0 中取最大值即可。 ::::

代码

//1.38s / 8.14MB / C++17 O2
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,k,l,r=1e12,mid,ans,a[1000010];
bool check(ll s){
    ll num=0;
    for(ll i=1;i<=n;i++){
        num+=max((ll)0,s-a[i]+1);
        if(num>s*k) return false;
    }return true;
}
int main(){
    // freopen("ice4.in","r",stdin);
    cin>>n>>k;
    for(ll i=1;i<=n;i++) cin>>a[i];
    while(l<r){
        mid=(l+r)/2+1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }cout<<l;
    return 0;
}