[bzoj1045][HAOI2008] 糖果传递【构造】

【题目链接】
　　http://www.lydsy.com/JudgeOnline/problem.php?id=1045
【题解】
　　记X[i]$X[i]$为从第i$i$堆向第i+1$i+1$堆转移的数量。（第n$n$堆转移到1$1$）
　　那么有a[i]−X[i]+X[i−1]=average$a[i]-X[i]+X[i-1]=average$
　　X[i]=a[i]+X[i−1]−average$X[i]=a[i]+X[i-1]-average$
　　移项得：X[1]=a[1]+X[n]−avarage$X[1]=a[1]+X[n]-avarage$
　　　　　　X[2]=a[2]+X[1]−avarage$X[2]=a[2]+X[1]-avarage$
　　　　　　=a[2]+a[1]+X[n]−2∗average$=a[2]+a[1]+X[n]-2\ast average$
　　　　X[i]=∑ij=1a[i]−X[n]−i∗avarage$X[i]=\sum _{j=1}^{i}a[i]-X[n]-i\ast avarage$
　　记S[i]=∑ij=1a[i]−i∗avarage$S[i]=\sum _{j=1}^{i}a[i]-i\ast avarage$
　有X[i]=S[i]−X[n]$X[i]=S[i]-X[n]$
　ans=∑ni=1|X[n]−S[i]|$ans=\sum _{i=1}^n|X[n]-S[i]|$
　当X[n]$X[n]$为S[i]$S[i]$中位数的时候ans$ans$取到最小值。
　复杂度O(nlog2n)$O(nlo{g}_{2}n)$

/* --------------
    user Vanisher
    problem bzoj-1045 
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    N       1000100
using namespace std;
ll read(){
    ll tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
ll a[N],cnt,n,s[N],ans,now;
int main(){
    n=read();
    for (ll i=1; i<=n; i++)
        a[i]=read(), cnt+=a[i];
    cnt=cnt/n;
    for (ll i=1; i<=n; i++)
        s[i]=a[i]-cnt+s[i-1];
    sort(s+1,s+n+1);
    now=s[(1+n)/2];
    for (ll i=1; i<=n; i++)
        ans=ans+abs(s[i]-now);
    printf("%lld
",ans);
    return 0;
}

同[bzoj1465][bzoj3293]