链接

• 点此跳转

思路

题目描述

有 nnn 个小朋友坐成一圈，每人有 aia_iai​ 颗糖果。

每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 111 。

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

分析

设 xix_ixi​ 表示第 iii 个朋友向第 i−1i-1i−1 个小朋友给的糖果数量。如下图所示：

根据题目要求，我们的目标为下面的式子：
min{∣x1∣+∣x2∣+...+∣xn∣}min\{|x_1| + |x_2| + ... + |x_n|\} min{∣x1​∣+∣x2​∣+...+∣xn​∣}

设平均数为 avgavgavg 。可以列出来如下方程：
{a1−x1+x2=avga2−x2+x3=avg⋮an−1−xn−1+xn=avgan−xn+x1=avg\left\{\begin{array}{c} a_{1}-x_{1}+x_{2}=a v g \\ a_{2}-x_{2}+x_{3}=a v g \\ \vdots \\ a_{n-1}-x_{n-1}+x_{n}=a v g\\ a_{n}-x_{n}+x_{1}=a v g \end{array}\right. ⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​a1​−x1​+x2​=avga2​−x2​+x3​=avg⋮an−1​−xn−1​+xn​=avgan​−xn​+x1​=avg​

移项，将未知量放在左边：
{x1−x2=a1−avgx2−x3=a2−avg⋮xn−1−xn=an−1−avgxn−x1=an−avg\left\{ \begin{aligned} x_{1}-x_{2} &= a_{1}-avg\\ x_{2}-x_{3} &= a_{2}-avg \\ & \vdots \\ x_{n-1}-x_{n} &= a_{n-1}-avg \\ x_{n}-x_{1} &= a_{n}-avg \\ \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧​x1​−x2​x2​−x3​xn−1​−xn​xn​−x1​​=a1​−avg=a2​−avg⋮=an−1​−avg=an​−avg​

从倒数第二行一直到第一行累加到最后一行得到（最后一行不动），再移项得：
{xn=x1−(avg−an)xn−1=x1−(2×avg−an−an−1)⋮x2=x1−((n−1)×avg−an−an−1−...−a2)x1=x1\left\{ \begin{aligned} x_{n} & =x_{1}-(avg-a_{n})\\ x_{n-1} & =x_{1}-(2\times avg-a_{n}-a_{n-1})\\ & \vdots \\ x_{2} & =x_{1}-((n-1)\times avg-a_{n}-a_{n-1}-...-a_{2})\\ x_{1} & = x_{1} \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧​xn​xn−1​x2​x1​​=x1​−(avg−an​)=x1​−(2×avg−an​−an−1​)⋮=x1​−((n−1)×avg−an​−an−1​−...−a2​)=x1​​

不妨设 x1x_1x1​ 为自由变量，用 x1x_1x1​ 表示其他变量。

观察 ∣xn∣=∣x1−(avg−an)∣|x_n| = |x_1-(avg-a_n)|∣xn​∣=∣x1​−(avg−an​)∣ ，可知在数轴上表示 x1x_1x1​ 到 avg−anavg-a_navg−an​ 的距离，其余变量也同理。

问题就转变为给定数轴上一些点，找到一个点到所有点的距离和最小。

这个问题的结论为：

• 点的个数为奇数时，中间的点满足条件。
• 点的个数为偶数时，中间两个点都满足条件。

证明如下。

1. 点的个数为奇数时

设最左边的点和最右边的点一组，依次这样两端为一组。

观察第 111 组，只有当点的取值在两点之间，到两点的距离之和最短。

• 因为若在两点之外，距离之和是两点距离 + 多出的距离。
• 所以只有在两点之间，到两点的距离之和为两点距离，也就是最短的。

同理，第 222 组，也是在两点之间的点，到两点的距离之和最短。

以此类推，可知 333 号点到所有点的距离之和最小，也就是中点。

2. 点的个数为偶数时

证明类似点为奇数时。

总结

所以我们求出来所以数轴上的点 （设为 bbb ），取中点，计算距离。

bbb 可以递推得到：
bi=bi+1+avg−aib_{i} = b_{i + 1} + avg - a_{i} bi​=bi+1​+avg−ai​

AC代码

// #pragma GCC optimize(3)
#include 
#include