牛牛的揠苗助长（二分&贪心）

题目传送门

假设水稻先不长，显然是数组中某一个数相等是最优的。依次类推

因此若不进行任何操作，数组变成数组

有：

然后将数组排序，显然当为奇数时，肯定是选取

当为偶数时也是选取，而不是选取

这里做个证明：

因为花费的公式为：

对于前者：将代入:

​
对于后者：将代入：
​

显然前者花费小。所以无论为奇数还是偶数,都是最优解。

因为当时能使所有数相等,那么都可以通过使那个要增加的数减1来保持相等。所以接下来用对答案不断二分就可以了。
时间复杂度：

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll a[N],n,ans,b[N];
bool jg(ll x){
    for(int i=1;i<=n;i++)
        b[i]=a[i]+x/n+(i<=x%n);
    sort(b+1,b+n+1);
    ll res=0;
    for(int i=1;i<=n;i++) res+=abs(b[i]-b[(n+1)>>1]);
    return  res<=x; 
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    ll l=1,r=1e14;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(jg(mid)) r=mid-1,ans=mid;
        else l=mid+1; 
    }
    printf("%lld\n",ans);
    return 0;
}