LINK：牛牛的揠苗助长
题目很水 不过做法很多 想到一个近乎O(n)的做法 不过感觉假了 最后决定莽一个主席树 当然 平衡树也行。
容易想到 答案为ans天 那么一些点的有效增长项数为 ans%n.
那么其实可以直接枚举答案到底在哪个位置 那么问题转换成了 需要最少多少次 每次可以给每个数+1或者-1 使得整个序列数字相等。
容易想到最后答案中位数 即排序后a[n/2+1]。这样排个序数一下前后缀和即可。
不过 每次动态+1 求动态中位数这件事情 可以利用一个右指针扫描什么的 不过存在一些细节。
可以考虑 主席树做 注意求答案的时候要 考虑清楚 到底还需多少天。
当然 还可以二分。一开始虽然想到二分了 但是没有细想 以为不具有单调性。
容易发现 如果比答案要大 考虑先变成答案的样子 多出来的 天数 和 多出来的增长数可以抵消掉。
非常巧妙的是 具有单调性了。关于证明：比答案<n时 可以考虑 如果中位数没有变化那么显然可以,如果变化了设当前答案为ans1 如果按照之前的中位数来做设答案为ans2 显然存在ans1<=ans2 且如果按照之前的ans2来做可以 那么按照当前中位数来做也可以。
当比答案>n时 跟上面一样类似的证明。
我写的是主席树的做法。
const int MAXN=100010;
int n,maxx,root,id,sum;
int a[MAXN];ll ans=INF;
struct wy{int l,r,sum;ll cnt;}t[MAXN*30];
inline void insert(int &p,int l,int r,int x,int w)
{
if(!p)p=++id;
if(l==r){sum(p)+=w;if(w==1)cnt(p)+=x;else cnt(p)-=x;return;}
int mid=(l+r)>>1;
if(x<=mid)insert(l(p),l,mid,x,w);
else insert(r(p),mid+1,r,x,w);
sum(p)=sum(l(p))+sum(r(p));
cnt(p)=cnt(l(p))+cnt(r(p));
}
inline int ask(int p,int l,int r,int x)
{
if(l==r)return l;
int mid=(l+r)>>1;
if(sum(l(p))>=x)return ask(l(p),l,mid,x);
return ask(r(p),mid+1,r,x-sum(l(p)));
}
inline ll query(int p,int l,int r,int L,int R)
{
if(L>R)return 0;
if(L<=l&&R>=r){sum+=sum(p);return cnt(p);}
int mid=(l+r)>>1;ll ww=0;
if(L<=mid)ww+=query(l(p),l,mid,L,R);
if(R>mid)ww+=query(r(p),mid+1,r,L,R);
return ww;
}
int main()
{
//freopen("1.in","r",stdin);
get(n);int ww=n/2+1;
rep(1,n,i)get(a[i]),maxx=max(maxx,a[i]);
++maxx;
rep(1,n,i)insert(root,1,maxx,a[i],1);
rep(1,n,i)
{
insert(root,1,maxx,a[i],-1);
insert(root,1,maxx,a[i]+1,1);
sum=0;int cc=ask(root,1,maxx,ww);
ll kk=query(root,1,maxx,1,cc-1);
ll cnt=(ll)sum*cc-query(root,1,maxx,1,cc-1);
//putl((ll)sum*cc-query(root,1,maxx,1,cc-1));
//putl(cnt);put(sum);put(cc);putl(query(root,1,maxx,1,cc-1));
sum=0;kk=query(root,1,maxx,cc+1,maxx);cnt+=kk-(ll)sum*cc;
if(!cnt){ans=min(ans,(ll)i);continue;}
int now=cnt%n==0?n:cnt%n;
if(i>=now)ans=min(ans,cnt+i-now);
else ans=min(ans,n-now+i+cnt);
}
putl(ans);
return 0;
}