这个题我没想到二分天数,然后又不知道一个数学定理:数列各个数到中位数的距离和最小,然后就很拉胯...
思路大概就是:首先对于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; }