「题解」糖果传递

我真是烦这种数学题啊，让人头秃。 ——某巨佬

一 题目

原题链接

描述

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。现要使每个小朋友获得均等糖果，请求出最小代价。

输入

小朋友个数n。下面n行 ai。

输出

求使所有人获得均等糖果的最小代价。

---

二 题解

这种题型大概有两种通解：费用流解法（如网络流24题中的负载平衡问题）和数学解法。但是解法一特别容易被卡MLE，能运行的数据范围大概只有$n\leqslant 100$，所以这题来谈谈数学解法。

假设有五个小朋友1,2,3,4,5，其中1号给了2号5颗糖，2号给了1号1颗糖，1号给了5号3颗糖，也可以看作1号给了5号3颗糖，2号给了1号-4颗糖。
于是可以得出一个结论，即任意一个人给别人的糖数总可以看作一个定值。假设1号只给5号糖，2号只给1号糖，……，5号只给4号糖，且给的糖数分别为$x_1,x_2,…,x_5$，那么$x_1,x_2,…,x_5$一定有绝对值最小的确定的值。现在我们要使$\sum\limits_{1\leqslant i\leqslant 5}|x_i|$最小，显然要求出这些“确定的值”。

因为每个人最终拿到的糖数为$\sum\limits_{1\leqslant i\leqslant n}a_i \div n$，设这个数为$\overline a$，则有以下等式：
$$\begin{aligned} & a_1 = \overline a - x_2 + x_1 \newline & a_2 = \overline a - x_3 + x_2 \newline & … \newline & a_5 = \overline a - x_1 + x_5 \end{aligned}$$
移项，得：
$$\begin{aligned} & x_2 = x_1 - (a_1-\overline a) \newline & x_3 = x_2 - (a_2 - \overline a) \newline & … \newline & x_5 = x_1 - (a_5 - \overline a)\end{aligned}$$
将前式分别带入后式可得：
$$\begin{aligned} & x_1 = x_1 \newline &x_2 = x_1 - (a_1-\overline a) \newline &x_3 = x_1 - (a_1 + a_2 - 2\overline a) \newline &… \newline &x_5 = x_1 - (a_1+a_2+a_3+a_4 - 4\overline a)\end{aligned}$$
可知：
$$ x_n = x_1 - (\sum\limits_{1\leqslant 1< n}a_i - (n-1)\times \overline a) $$

设$c_1 = a_1 - \overline a,c_2 = a_1 + a_2 - 2\overline a,…$，以此类推，可知$x_n = x_1 - c_{n-1}$。同时有递推式$c_i = c_{i-1} + a_i - \overline a$。这个递推式与$x$取值无关，且总有$c_0 = 0$，因此可以计算出所有$c_i$的值。

又有$x_2 = x_1 - c_1,x_3= x_1- c_2,…$，则$\sum\limits_{1\leqslant i\leqslant 5}|x_i|$可表示为：
$$ |x_1| + |x_1 -c_1| +|x_1-c_2| + … +|x_1-c_4| $$
这也可以看作数轴上每个$c_i$到$x_1$的距离之和。那么我们就要找一个$x_1$，使得在数轴上它到每个$c_i$的距离最小。这个$x_1$即是$c_1,c_2,…,c_4$的中位数。

证明
先把$c_1,c_2,…,c_4$排好序，表示在数轴上，如下图所示。

任取一$x_1$，则距离之和可以化为$\text{dist}(c_1,c_4) + \text{dist}(c_2,c_3) +2\times \text{dist}(c_2,x_1)$。其中$\text{dist}(c_1,c_4) + \text{dist}(c_2,c_3)$为定值，那么让$\text{dist}(c_2,x_1) $最小一定会更优一点。它的最小值为$0$，此时$x_1$选在$c_2$上。
归纳，可知将$x_1$选在$c_1\text{~}c_4$中的一个点上一定要优一点。

然后再分别尝试$c_1,c_2,…,c_4$这些点，不难发现$x_1$选的越靠中间距离之和越小，故可知$x_1$取$c_1,c_2,…,c_4$的中位数。

那么$x_1$就很好求了，于是我们就解决了这个问题。注意当$n$为偶数时，两个中位数取哪一个都可以。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define LL long long

LL read(){ 
    LL s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=((s<<1)+(s<<3))+c-'0';
    return s*ne;
}

const int CN=1e6+6;

LL n,x1,a[CN],c[CN],_a;
LL llabs(LL a) {return a>0 ? a:-a;}

int main()
{
    n=read();
    LL sigma = 0;
    for(int i=1;i<=n;i++) 
        a[i] = read(),sigma += a[i];
    _a = sigma/n; //求平均值 
    
    c[0] = 0;    
    for(int i=1;i<=n;i++)
        c[i] = c[i-1]+a[i]-_a; //递推c[i]
            
    sort(c+1,c+n+1);
    x1 = c[(n+1)/2]; //计算中位数
        
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans += llabs(x1-c[i]); //求代价
    printf("%lld\n",ans);
    
    return 0;
}