糖果传递-题解

查看原题请戳这里
怎么说呢，这道题貌似需要用式子来表示出每个小盆友的代价，才可以理解这道题的做法。
对于每一个小盆友，他最终的糖果数是一定要等于平局数的。所以，我们用a表示小盆友原有的糖果，xn表示他给上一个小盆友的苹果数，x(n + 1)表示他的下一个小盆友给他的糖果数，则有： 对于第1个小朋友，A1-X1+X2=ave -> X2=ave-A1+X1 = X1-C1(假设C1=A1-ave，下面类似） 对于第2个小朋友，A2-X2+X3=ave -> X3=ave-A2+X2=2ave-A1-A2+X1=X1-C2 对于第3个小朋友，A3-X3+X4=ave -> X4=ave-A3+X3=3ave-A1-A2-A3+X1=X1-C3 …… 对于第n个小朋友，An-Xn+X1=ave。 至于如何确定X1的值，我们去中位数即可。(不懂的可以看货仓选址问题）
附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;
ll n,a[1000005],ans,sum,p,s[1000005];
int main()
{
    scanf(“%lld”,&n);
    for(register int i = 1; i <= n; i++)
    {
        scanf(“%lld”,&a[i]);
        sum += a[i];
    }
    p = sum / n;
    for(register int i = 1; i <= n; i++) a[i] -= p;
    for(register int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    sort(s + 1, s + n + 1);
    int t = s[(n + 1) >> 1];
    for(register int i = 1; i <= n; i++) ans += fabs(t - s[i]);
    printf(“%lld”,ans);
    return 0;
}