糖果传递问题

题目描述

有 $n$ 个小朋友坐成一圈，每人有 $a[i]$ 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 $1$。

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

输入格式

第一行输入一个正整数 $n$，表示小朋友的个数。

接下来 $n$ 行，每行一个整数 $a[i]$，表示第 $i$ 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

输入输出样例 #1

输入 #1

4
1
2
5
4

输出 #1

4

输入输出样例 #2

输入 #2

5
1
2
3
4
5

输出 #2

5

限制条件

• $1 \le n \le 1000000$
• $0 \le a[i] \le 2 \times 10^9$
• 数据保证一定有解

样例解释 #1

初始糖果数：$[1, 2, 5, 4]$

平均糖果数：$\frac{1+2+5+4}{4} = 3$

需要传递糖果使每人都有 $3$ 个糖果。

一种最优方案：

1. 第 3 个小朋友给第 2 个小朋友 $1$ 个糖果（第 2 个小朋友现在有 $3$ 个，第 3 个有 $4$ 个）
2. 第 3 个小朋友给第 4 个小朋友 $1$ 个糖果（第 4 个小朋友现在有 $5$ 个，第 3 个有 $3$ 个）
3. 第 4 个小朋友给第 1 个小朋友 $2$ 个糖果（第 1 个小朋友现在有 $3$ 个，第 4 个有 $3$ 个）

总传递糖果数：$1 + 1 + 2 = 4$，代价为 $4$。

数学模型

设最终每人糖果数为 $avg = \frac{\sum_{i=1}^n a[i]}{n}$。

设 $x_i$ 表示第 $i$ 个小朋友给第 $i-1$ 个小朋友的糖果数（正数表示给，负数表示收）。

则对于第 $i$ 个小朋友： $a[i] - x_i + x_{i+1} = avg$ （注意 $x_{n+1} = x_1$，因为是环形）

整理得： $x_{i+1} = x_i + (avg - a[i])$

令 $c_i = \sum_{j=1}^i (a[j] - avg)$，则有： $x_{i+1} = x_1 - c_i$

总代价为 $\sum_{i=1}^n |x_i|$。

问题转化为：求一个 $x_1$，使得 $\sum_{i=1}^n |x_1 - c_{i-1}|$ 最小（其中 $c_0 = 0$）。

这是一个经典的货仓选址问题，最优解为取 $c_{i-1}$ 的中位数作为 $x_1$。

算法步骤

1. 计算平均值 $avg$
2. 计算前缀和 $c_i = \sum_{j=1}^i (a[j] - avg)$
3. 将 $c$ 数组排序
4. 取中位数 $mid = c_{\lfloor \frac{n}{2} \rfloor}$
5. 计算 $\sum_{i=0}^{n-1} |mid - c_i|$ 即为答案