参考小呆呆老师:https://www.acwing.com/solution/content/5531/
这个题解中使用的方法基于一个数学性质:对于一组数,使它们所有数都变成同一个数(本题中即为平均数),变化的总代价最小的方法是让所有数变成这组数的中位数。这个性质可以通过数学证明来解释,其基本思想是中位数到所有点的距离之和最小。
在本题的上下文中,每个小朋友手里的糖果数减去平均数后的结果可以看作是每个小朋友相对于平均值的“偏移量”。如果每个人都有平均数个糖果,那么这些偏移量的和应该为0。因此,我们的目标是通过最少的代价(传递糖果的次数),调整这些偏移量,使得每个人的偏移量都为0。
为什么要排序呢?因为排序后的前缀和数组中的中位数,实际上代表了达到平衡(所有偏移量为0)所需要移动糖果的“中心点”。这样,距离这个中心点最远的偏移量(即排序后数组两端的偏移量)需要最多的移动次数来调整,而靠近中心点的偏移量需要的移动次数则相对较少。
通过对前缀和数组排序,我们实际上是在找一个“最优的平衡点”,这个点到所有其他点的距离之和最小。然后,计算所有点到这个“平衡点”的距离之和,就能得到使所有人获得均等糖果的最小代价。
这里的“距离”实际上是通过糖果传递次数来衡量的,每传递一次糖果代价为1。因此,这种方法可以确保在所有小朋友间分配糖果达到均等所需的总代价最小。
可能会看不懂(比如我),下面是更进一步的解释:
为什么我们要用到“前缀和”的中位数。
想象你和你的朋友们围成一圈,每个人手里都有一些糖果。老师要求大家通过传递糖果,使得每个人手里的糖果数量都一样。但是,每次传递糖果都会消耗一些力气,我们的目标是尽可能少地消耗力气。
现在,我们先假设大家都有一个小袋子,开始时袋子里的糖果数就是每个人手里的糖果数减去平均数后的结果。这样,有的袋子里可能是正数(表示这个人的糖果比平均数多),有的可能是负数(表示糖果比平均数少)。
为什么直接根据这个“正数或负数”的结果来传递糖果可能会很乱,也可能会花更多的力气呢?因为如果我们只看一个人的糖果比平均数多还是少,然后直接做调整,可能会忽略了周围人的实际情况。比如,一个人可能需要给左边的人传递糖果,同时也需要从右边的人那里接收糖果,这样会造成很多不必要的“来回传递”,增加了大家的总体力气消耗。
这时候,“前缀和”的概念就派上用场了。我们不是单独看每个人的糖果多少,而是从一个起点开始,一直加上每个人的“多或少”,这样就记录了从起点开始到当前点为止,大家总共需要传递的糖果数。通过这样的方式,我们就能更好地看到整个圈子中糖果是如何需要被传递的。
然后,为什么要找这个“前缀和”的中位数呢?因为中位数在统计学中是一个很神奇的数字,它能够代表一组数字的“中心位置”。当我们把前缀和排序后找到中位数,这个中位数其实就像是一个“平衡点”——从这个点出发,向左向右分配糖果,能够使得总的传递次数(也就是大家的总体力气消耗)最小。这是因为中位数把所有人分成了两半,确保了每一边的人传递糖果的次数尽可能地少,避免了不必要的“来回传递”。
所以,通过找到这个“平衡点”,我们就能用最省力气的方式,让每个人的糖果数都一样,实现了老师的要求。这就是为什么我们要用“前缀和”的中位数来帮助我们达成目标的原因。
import java.util.*;
public class Main{
static final int N = 1000010;
static int[] s = new int[N];
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
int n = sca.nextInt();
long sum = 0;
for (int i = 1; i <= n; i++ )
{
s[i] = sca.nextInt();
sum += s[i];
}
int avg = (int)(sum / n);
for (int i = 1; i <= n; i++ )
{
s[i] = s[i] - avg + s[i - 1];
}
Arrays.sort(s, 1, n + 1);
long res = 0;
for (int i = 1; i <= n; i++ )
{
res += Math.abs(s[i] - s[(n + 1) / 2]);
}
System.out.println(res);
}
}