贪心算法（算法竞赛、蓝桥杯）--糖果传递

1、B站视频链接：A31 贪心算法 P2512 [HAOI2008] 糖果传递_哔哩哔哩_bilibili

题目链接：[HAOI2008] 糖果传递 - 洛谷

#include

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;

}

精彩内容

 您阅读本篇文章共花了：