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

题目传送门

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

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

有： $b[i]=a[i]+\dfrac{day}{n}+(i<=day\%n)$

然后将数组 $b$ 排序，显然当 $n$ 为奇数时，肯定是选取 $b[\dfrac{n+1}{2}]$

当 $n$ 为偶数时也是选取 $\dfrac{n+1}{2}=\dfrac{n}{2}$ ，而不是选取 $\dfrac{n}{2}+1$

这里做个证明：

因为花费的公式为： $cost=i\times b[i]-\sum\limits_{j=1}^{i}b[i]+\sum\limits_{j=i+1}^{n}b[i]-(n-i)\times b[i]$

对于前者：将 $i=\dfrac{n}{2}$ 代入:

$cost_{pre}=\sum\limits_{j=\frac{n}{2}+1}^{n}b[i]-\sum\limits_{j=1}^{\frac{n}{2}}b[i]$
对于后者：将 $i=\dfrac{n}{2}+1$ 代入： $cost_{pre}=\sum\limits_{j=\frac{n}{2}+1}^{n}b[i]-\sum\limits_{j=1}^{\frac{n}{2}}b[i]+b[\frac{n}{2}+1]$

显然前者花费小。所以无论 $n$ 为奇数还是偶数, $i=\dfrac{n+1}{2}$ 都是最优解。

因为当 $day=ans$ 时能使所有数相等,那么 $day=ans+1,ans+2\dots$ 都可以通过使那个要增加的数减1来保持相等。所以接下来用对答案不断二分就可以了。
时间复杂度： $O(nlogn\times logn)$

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;
}