题目描述
有 $n$ 个小朋友坐成一圈,每人有 $a[i]$ 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 $1$。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 $n$,表示小朋友的个数。
接下来 $n$ 行,每行一个整数 $a[i]$,表示第 $i$ 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数,表示最小代价。
数据范围
$1 \le n \le 1000000$,
$0 \le a[i] \le 2 \times 10^9$,
数据保证一定有解。
输入样例:
4
1
2
5
4
输出样例:
4
/*
假设 n 个小朋友,每个人的糖果为 a[1], a[2], a[3], ... , a[n]
a[1] 给 a[2] 的糖果数量为 b[1]
a[2] 给 a[3] 的糖果数量为 b[2]
..........................
a[n] 给 a[1] 的糖果数量为 b[n]
设 ave = (a[1] + a[2] + a[3] + ... + a[n]) / n;
b[1] = b[1]
b[2] = b[1] + (a[2] - ave)
b[3] = b[2] + (a[3] - ave)
.........................
b[n] = b[n - 1] + (a[n] - ave)
对上述式子进行等价变形:
b[1] = b[1]
b[2] = b[1] + (a[2] - ave)
b[3] = b[1] + (a[2] + a[3] - 2 * ave)
...............
b[n] = b[1] + (a[2] + a[3] + ... + a[n] - (n - 1) * ave)
由上式可知,只要 b[1] 确定了,所有数就都确定了
由于,给的糖果数量可以为负数,相当于获得糖果
故: ans = |b[1]| + |b[2]| + ... + |b[n]|.
此时,最关键的一步来了,将上述式子再做变形,将其映射成数轴上两点之间的距离
|b[1]| = |b[1] - 0|
|b[2]| = |b[1] - (ave - a[2])|
|b[3]| = |b[1] - (2 * ave - a[2] - a[3])|
......................................
|b[n]| = |b[1] - ((n - 1) * ave - a[2] - a[3] - ... - a[n])|
令:
c[1] = 0
c[2] = ave - a[2]
c[3] = 2 * ave - a[2] - a[3]
........................
c[n] = (n - 1) * ave - a[2] - a[3] - ... - a[n]
则:
ans = |b[1] - c[1]| + ... + |b[1] - c[n]|
则此题变为仓库选址原题,易知当 b[1] 取 c[1~n] 的中位数时,和最小,也即代价最小
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int s[N], c[N];
int n;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i ++)
{
cin >> s[i];
s[i] += s[i - 1];
}
int ave = s[n] / n;
c[1] = 0;
for(int i = 2;i <= n;i ++)
{
c[i] = (i - 1) * ave - s[i] + s[1];
}
sort(c + 1, c + n + 1);
int b1 = c[(1 + n) / 2];
int res = 0;
for(int i = 1;i <= n;i ++)
{
res += abs(b1 - c[i]);
}
cout << res << endl;
return 0;
}