C 牛牛的揠苗助长

开篇的一个结论：
最优策略：倘若不考虑水稻每段时期的自增，仅人为增加/减少，那么所有水稻必定向某一水稻对齐(==a[?])
反证法：
将水稻从小到大排列，假定在某高度x,(x不等于任意水稻,x>a[i]&&x<a[i+1])，取得最优策略ans;
令x-1，newans=ans-i+(n-(i+1)+1)=ans+n-2i;
令x+1, newans=ans+i-(n-(i+1)+1)=ans-n+2i;
n-2i与-n+2i中必定有一个小于0
故所有水稻必定向某一水稻对齐(==a[?])，最优高度一定是等于某一水稻
最少次数(过了多少天)：

ans = b[i] * (i) - s[i] + (s[n] - s[i]) - (n - i) * b[i];

加上题设条件，每隔一段时间自增,假设过了ans天，则针对某一a[i]来说，a[i]=(ans/n)+(i<=ans%n);
由于都进行了ans/n次自增，可省略，前ans%n天自增即可
对时间进行二分，判断在ans天内是否可以使得所有水稻对齐
（另：倘若ans天可以对齐，那么ans+1天也可对齐，第ans+1天使得自增得水稻减下去就可)

#pragma warning (disable :4996)
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,l,r) for(int i=l;i>=r;--i)
#define clr(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const double PI = cos(-1.0);
const double eps = 1e-12;

ll n;
ll a[101000], b[101000], s[101000];
ll le, ri;

bool check(ll ans) {
    rep(i, 1, n) b[i] = a[i];
    rep(i, 1, ans % n) ++b[i];
    sort(b + 1, b + 1 + n);
    rep(i, 1, n) s[i] = s[i - 1] + b[i];
    rep(i, 1, n) 
        if (b[i] * (i) - s[i] + (s[n] - s[i]) - (n - i) * b[i] <= ans) return 1;
    return 0;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    le = 0, ri = 1ll << 62;
    while (le + 1 < ri) {
        ll mid = (le + ri) >> 1;
        if (check(mid)) ri = mid;
        else le = mid;
    }
    cout << ri << "\n";


    return 0;
}