solution

显然答案具有单调性,如果答案为c。而对于任意一个,我们都可以在(c+1)~a的这些天里,让生长1的那个植株减1.

所以我们考虑二分答案,如果我们二分了一个答案x,我们可以先让那些水稻按照规则生长x天,最后再进行最多x次操作使他们高度相同即可。

那么现在问题就变为了,已经知道所有水稻高度,最少操作多少次使得所有水稻高度相同,显然最终高度肯定是现有水道中的一个,所以先排个序,然后枚举一下最终高度,计算一下操作次数即可。
复杂度

code

/*
* @Author: wxyww
* @Date: 2020-05-08 19:23:58
* @Last Modified time: 2020-05-08 19:50:01
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll sum[N],n,a[N],b[N];
bool check(ll x) {
    ll t = x % n,k = x / n;
    for(int i = 1;i <= n;++i)
        b[i] = a[i] + k + (i <= t);
    sort(b + 1,b + n + 1);
    for(int i = n;i >= 1;--i) sum[i] = sum[i + 1] + b[i];
    ll s = 0,ret = 1e18;
    for(int i = 1;i < n;++i) {
        ret = min(ret,(i - 1) * b[i] - s + sum[i + 1] - b[i] * (n - i));
        s += b[i];
    }
    return ret <= x;
}
int main() {

    n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    ll l = 1,r = 1e15;

    ll ans = 0;

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

    cout<<ans;
    return 0;
}