1、B站视频链接:A31 贪心算法 P2512 [HAOI2008] 糖果传递_哔哩哔哩_bilibili
题目链接:[HAOI2008] 糖果传递 - 洛谷
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,a[N],c[N];
long long b,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b+=a[i];
}
b=b/n;
for(int i=2;i<=n;i++){
c[i]=c[i-1]+a[i-1]-b;
}
sort(c+1,c+1+n);
for(int i=1;i<=n;i++){
ans+=abs(c[i]-c[(n+1)/2]);//取中位数
}
printf("%lld\n",ans);
return 0;
}