牛客练习赛63 C.牛牛的揠苗助长

考虑到要找最小天数，我们二分天数k，然后判断是否满足即可。在check函数中，我们找出在不用魔法时k天后各个秧苗高度，用b[N]表示，然后问题转化为对数组b进行最多k次操作，是否能将b[N]各个数变相等，显然我们可以枚举b[N],设当前b[i]为x,然后将x作为最终的值，再对b[N]作差值，求出当前费用，如果当前费用小于k，则说明满足条件。显然这总做法每次求费用为O(n),每进行一次check为O(n^2),因此，我们可以利用前缀和思想，将b[N]排序，记录b[N]的前缀和sum[N]，然后在枚举b[N],这样每次的费用就为
,
这样可以在O(1)时间求费用，由于用了sort所以每次check复杂度为nlog(n),总复杂度为nlog(n)log(n)
附代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005],b[100005],sum[100005];
int n;
int cheak(ll x){
    ll t=x/n,k=x%n;
    ll xx=1e18;
    for(int i=1;i<=n;i++){
        b[i]=a[i]+t;//求b[N]
        if(k)b[i]++,k--;
        xx=min(xx,b[i]);
    }
    for(int i=1;i<=n;i++)b[i]-=xx;//我们求出最小值，将b[N]减去最小值，防止sum爆long long
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
    for(ll i=1;i<=n;i++){
        if(b[i]*(i-1)-sum[i-1]+(sum[n]-sum[i-1])-(n-i+1)*b[i]<=x)return 1;
    }
    return 0;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll l=1,r=1e18;
    while(l<r){
        ll mid=(l+r)>>1;
        if(cheak(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
}
int main(){
    solve();
    return 0;
}