lc122. 糖果传递（排序 中位数 递推 贪心）

有 nn 个小朋友坐成一圈，每人有 a[i]a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 11。
求使所有人获得均等糖果的最小代价。

输入格式

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

输出格式

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

数据范围

1≤n≤10000001≤n≤1000000,
0≤a[i]≤2×1090≤a[i]≤2×109,
数据保证一定有解。

输入样例：

4 1 2 5 4

输出样例：

4

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
LL s[N], c[N];
LL n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> s[i], s[i] += s[i - 1];
    LL avg = s[n] / n;
    for (int i = 2; i <= n; ++i) c[i] = (i - 1) * avg - (s[i] - s[1]);
    sort(c + 1, c + n + 1);
    LL mid = c[(n + 1) / 2];
    LL res = 0;
    for (int i = 1; i <= n; ++i) res += abs(c[i] - mid);
    cout << res << endl;
    return 0;
}