AcWing 122. 糖果传递
原题链接
中等
作者:
隐灵
,
2024-03-25 15:58:35
,
所有人可见
,
阅读 2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
typedef long long LL;
int n;
int a[N];
LL c[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
LL sum = 0;
for (int i = 1; i <= n; i ++ ) sum += a[i]; //求糖果总和
LL avg = sum / n; //求糖果平均数
for (int i = n; i > 1; i -- )
c[i] = c[i + 1] + avg - a[i]; //用结论
c[1] = 0;
sort(c + 1, c + n + 1);
LL res = 0;
for (int i = 1; i <= n; i ++ ) res += abs(c[i] - c[(n + 1) / 2]);
printf("%lld", res);
return 0;
}