有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
第一行一个正整数n<=1000000，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的
糖果的颗数．
求使所有人获得均等糖果的最小代价。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int maxn=2000000+10; int a[maxn]; ll sum1; int sum[maxn],b[maxn]; int n; int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); sum1+=a[i]; } sum1/=n; for (int i=1;i<=n;i++){ b[i]=a[i]-sum1; } for (int i=1;i<=n;i++){ sum[i]=sum[i-1]+b[i]; } sort(sum+1,sum+1+n); int k=sum[n/2+1]; long long ans=0; for (int i=1;i<=n;i++){ ans+=abs(sum[i]-k); } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/lmjer/p/8970610.html