数学真的是太奇妙了。n个人分糖果,这里我们先计算平均数。得到平均数之后,我们用原来的糖果减去平均数,这样就是每个人需要支出的糖果数。我们把这些数看成是价值,然后排序,找到中位数,把每个人都变成中位数会产生一个价值,把这些价值加起来就是总共的价值啦。


代码:

StatusAccepted
Time2176ms
Memory9104kB
Length572
LangC++
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1000005
int res[MAX];
int val[MAX];
int n, all;
long long ans, avg;
int main()
{
    while(~scanf("%d", &n)){
        ans = 0;
        avg = 0;
        for(int i=1;i<=n;i++){
            scanf("%d", &res[i]);
            avg+=res[i];
        }
        avg/=n;
        for(int i=1;i<=n;i++)val[i]=val[i-1]+res[i]-avg;
        sort(val+1, val+n+1);
        avg = val[n/2+1];
        for(int i=1;i<=n;i++)ans+=abs(val[i]-avg);
        printf("%lld\n", ans);
    }
    return 0;
}