Spreading the Wealth UVA - 11300

思维 中位数 T2 Spreading the Wealth - UVA 11300 - Virtual Judge --- 传播财富 - UVA 11300 - 虚拟评委 (csgrandeur.cn)

圆桌旁坐着n个人，每人有一定数量的金币，金币总数能被n整除。

每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。

你的任务是求出被转手的金币数量的最小值。

比如，$n＝4$，且 $4$ 个人的金币数量分别为 $1，2，5，4$ 时，只需转移 $4$ 枚金币（第 $3$ 个人给第 $2$ 个人两枚金币，第 $2$ 个人和第 $4$ 个人分别给第 $1$ 个人 $1$ 枚金币）即可实现每人手中的金币数目相等。

输入

输入包含多组数据。每组数据第一行为整数$n$（$n\le 1000000$），以下$n$行每行为一个整数，按逆时针顺序给出每个人拥有的金币数。

输入结束标志为文件结束符（EOF）。

输出

对于每组数据，输出被转手金币数量的最小值。输入保证这个值在64位无符号整数范围内。

样例

输入

3
100
100
100
4
1
2
5
4

输出

0
4

思路

是个挺复杂的问题, 考虑建模进一步思考。

每个位置可以往相邻位置给金币, 也可以从相邻位置接受金币, 我们需要用代数的方法描述出来这个变化。与其用两个变量代表给的金币和接收的金币, 不如用一个变量 $x_i$ 代表, 若 $x_i>0$ 则说明是从 $i$ 得到金币 $x_i$ 个, 若 $x_i<0$ 则说明是向 $i$ 给予金币 $x_i$ 个。

将一个数组中所有数通过加减使整个数组的值相同, 其结果一定是所有数的平均值, 这个在题目中也有暗示, “金币总数能被n整除”。

设这个平均值为 $M$, 编号为 $i$ 的人初始有 $A_i$ 个金币, 则 $i$ 位置需要改变的金币就可以用这个式子描述：$A_i-x_i+x_{i+1}=M$ 其中 $x_i$ 代表 $i$ 位置 给 $i-1$ 位置的金币数, 若为负数则是从 $i-1$ 拿走 $|x_i|$ 个金币。因此这样建模就可以显著降低复杂度, 不需要额外考虑方向问题。

接下来就是从这 $n$ 个方程式中解出 $x_i$ 的值, 并找到最小的那个, 为了方便考虑, 我们进行变量分离：$x_{i+1}=x_i+(M-A_i)$ 可以发现, $x_{i+1}$ 可以被 $x_i$ 推出来, 根据 $A_1-x_1+x_2=M$ 可以得出 $x_2=x_1+M-A_i$, 进而得出 $x_3=x_1+2M-A_1-A_2$。

再令 $C_1=M-A_1,C_2=2M-A_1-A_2,\dots$ 。而我们要求的是 所有 $x_i$ 的绝对值之和最小值, 即 $|x_1|+|x_1-C_1|+|x_1-C_2|+\cdots +|x_1-C_n-1|$ 最小。

显然 $C$ 是一个可以被算出来的常数, 那么我们的问题就转换成了, 给定数轴上 $n$ 个点, 找到 点$x_1$ 使得 $x_1$ 到 $C_i$ 的距离总和最小。

而这种问题的答案就是所有 $C_i$ 的中位数。求出之后再与所有 $C_i$ 作差求和即可得到最小总和。

代码

#include <bits/stdc++.h>
using namespace std;
// #define debug
const int N = 1e6 + 10;
typedef long long LL;
int n;
int a[N], c[N];
 
void solve()
{
    LL sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    LL m = sum / n;
    c[0] = 0;
    for (int i = 1; i < n; i++)
        c[i] = c[i - 1] + a[i] - m;
    sort(c, c + n);
    LL mid = c[n / 2], res = 0;
    for (int i = 0; i < n; i++)
        res += abs(c[i] - mid);
    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n)
    {
        solve();
    }
 
    return 0;
}