https://loj.ac/problem/10010

题目描述

  有\(n\)个小朋友坐成一圈，每人有\(a_i\)颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为\(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 - \sum_{j=1}^{i}{a[j]}\)

  那么我们求得就是\(ans=| p_1 | + | p_1 - x_1 |＋| p_1 - x_2 |+……| p_1-x_n|\)

  这就是求\(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;
}