这个题我没想到二分天数,然后又不知道一个数学定理:数列各个数到中位数的距离和最小,然后就很拉胯...
思路大概就是:首先对于day来二分,group=day/n,代表经过了几轮,remain=day%n,表示在最后当前的一轮中有几天已经过去了。然后对于每个点临时的temp[i]=group+a[i],如果还有remain存在,那temp[i]+=1.最后根据那个数学定理:数列各个数到中位数的距离和最小。可以知道,当前最小的手动操作天数sum即为abs(temp[i]-temp[n/2+1])的和;最后二分条件判断一下缩小范围,时间复杂度O(nlogn).赛场上没写出来太菜了

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define endl '\n'
using namespace std;
const int maxn=1e5+5;
int a[maxn],temp[maxn],n;
ll check(ll day){
    ll group=day/n;ll remain=day%n;
    for(int i=1;i<=n;i++){
        temp[i]=group+a[i];
        if(remain){
            temp[i]+=1;remain-=1;
        }
    }
    sort(temp+1,temp+n+1);
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=abs(temp[i]-temp[n/2+1]);
    }
    return sum<=day;
}
int main(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    ll l=1,r=1e18;
    while(l<r){
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
}