AcWing 122. 糖果传递
原题链接
中等
作者:
全都是你
,
2023-03-22 22:06:49
,
所有人可见
,
阅读 108
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
long long a[N], c[N];
int n;
int main()
{
cin >> n;
long long sum = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
sum += a[i];
}
long long avg = sum / n;//平均数
for (int i = n; i > 1; i -- ) c[i] = c[i + 1] + avg - a[i];
c[1] = 0;
long long res = 0;
sort(c + 1, c + n + 1);
for (int i = 1; i <= n; i ++ )
{
res += abs(c[i] - c[(i + 1) / 2] );
}
cout << res;
return 0;
}