题目描述
有n个小朋友坐成一圈，每人有ai颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为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个数的中位数
代码
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;
}