题目描述

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

输入格式

第一行包含一个正整数 $n$ ($n \leq 10^6$)，表示小朋友的个数。

接下来的 $n$ 行，每行包含一个正整数 $a_i$ ($\sum a_i < 2^{31}$)，表示第 $i$ 个小朋友得到的糖果的颗数。

输出格式

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

题解

记最终每个人得到的糖果数为 $\bar a$ ($\bar a = \dfrac 1n \sum\limits_{i=1}^n a_i$)，令 $b_i = a_i - \bar a$，易得用 $b_i$ 代替 $a_i$，所得的答案不变，且最终每个数都会变为 $0$。

在一个方案中，考虑每相邻两人之间的累计传递，可以看作是其中一个人给另一个人，或没有传递 (比如说总共是 A 给了 B $6$ 颗糖果或 B 给了 A $4$ 颗糖果)，总之可以用一个整数 $x_i$ (可正可负) 表示。那么，记 $x_i$ 表示最终累计 $i$ 给了 $i+1$ 多少颗糖果 (类似地，负数就代表 $i+1$ 给了 $i$)，由于最终糖果数均为 $0$，则有 $$ a_i + x_{i-1} - x_i = 0 $$

可以看出，答案就是 $\sum\limits_{i=1}^n \left| x_i \right|$，因此我们就要最小化 $x_i$。

可以发现，这里一共有 $n$ 个方程，但是其中独立的只有 $n-1$ 个 (任意一个方程都能由剩余 $n-1$ 个方程线性得出)，于是我们假定 $t = x_1$，则有

\begin{array}l x_2 = a_2 + x_1 = a_2 + t \\ x_3 = a_3 + x_2 = a_3 + a_2 + t \\ x_4 = a_4 + x_3 = a_4 + a_3 + a_2 + t \\ \cdots \\ x_n = a_n + x_{n-1} = a_n + \cdots + a_2 + t \end{array}

记 $s_i = \sum\limits_{k=2}^i a_k$，问题转移成了最小化 $$ \sum_{i=1}^n \left| s_i + t \right| $$

换元 $x = -t$ 后，由几何意义可以得知，就是在数轴上寻找一点，使得与 $n$ 个已知点的距离之和最小。很显然，当这个点为这组数据的中位数时，取得最小值。

于是我们只需要求个前缀和然后排个序就可以得到答案了，当然，求中位数可以直接 $O(n)$ 得到 (nth_element())。

代码

#include <bits/stdc++.h>
#define N 1024404
using namespace std;

typedef long long ll;

int n, i, j;
ll s, a[N];

int main(){
    scanf("%d", &n); s = 0;
    for(i = 1; i <= n; ++i) {scanf("%lld", a + i); s += a[i];} s /= n;
    for(i = 1; i <= n; ++i) a[i] += a[i - 1] - s;
    nth_element(a + 1, a + (j = n + 1 >> 1), a + (n + 1)); s = 0;
    for(i = 1; i <= n; ++i) s += abs(a[i] - a[j]);
    printf("%lld\n", s);
    return 0;
}

坑

坑1：不要被 $\sum a_i < 2^{31}$ 迷惑住了，这题由于有各种减法运算照样是需要 $64$ 位整数的！