题目描述
有n个小朋友坐成一圈，每人有a颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为1。求使所有人获得均等糖果的最小代价。
思路
个人感觉这道题的贪心策略还是比较难想的，刚开始没有任何思路。首先我们设平均数为average，p[i]表示 i 给 i - 1 的糖果数。所以可以得到以下几个等式：
a[ 1 ] + p[ 2 ] - p[ 1 ]=average
a[ 2 ] + p[ 3 ] - p[ 2 ]=average
a[ 3 ] + p[ 4 ] - p[ 3 ]=average
……
那么我们把它们化简：
p[ 2 ] = p[ 1 ] + average - a[ 1 ]
p[ 3 ] = p[ 2 ] + average - a[ 2 ] = p[ 1 ] + 2*average - a[ 1 ] - a[ 2 ]
p[ 4 ] = p[ 3 ] + average - a[ 3 ] = p[ 1 ] + 3*average - a[ 1 ] - a[ 2 ] -a [ 3 ]
……
我们再设x[ i ] = i*average - ∑a[ j ] (1 ≤ j ≤ i)
那么我们求得就是ans=| p[ 1 ] | + | p[ 1 ] - x [ 1 ] |＋| p[ 1 ] - x [ 2 ] | + ……
这就是求p[ 1 ]到 x[ 1 ]，x[ 2 ]，……，x[ n ] 这几个点的距离，那么p[ 1 ]的值即为这n个数的中位数
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[1010000],x[1010000]; int main() { ll n,sum=0; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum+=a[i]; } sum=sum/n; ll ans=0; for(int i=1;i<=n;i++) x[i]=x[i-1]+sum-a[i]; sort(x+1,x+n+1); int k=x[(n+1)/2]; for(int i=1;i<=n;i++) ans+=abs(k-x[i]); printf("%lld",ans); return 0; }