首先,定义 xi 为 i 给 i-1多少个硬币;记平均数为M
可得到n-1个方程 A1(原来i有的硬币)- x1 + x2 = M; A2 - x2 + x3 = M; ..... 特别说明第n个方程可由前n-1个推出,所以去掉;
将式子变形 x2 = x1 + M - A1; x3 = x1 + 2*M - A1 - A2; .....
记A1 - M 为 c1 ; A1 + A2 - M 为 c2 ; 。。。。
则最终要求的为 | x1- 0 | + | x1 - c1 | + | x1 - c2 ..... | x1 - cn-1|;
则 只需求一中位数即可;
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 1e6 + 100; LL a[maxn],n,b[maxn]; int main() { while(scanf("%lld",&n)==1){ LL all = 0; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); all+=a[i]; } int M = all/n; int summ = 0,sumhe = 0; for(int i=1;i<=n;i++){ b[i] = sumhe -summ; sumhe+=a[i]; summ+=M; } sort(b+1,b+n+1); int mid = n/2; LL res = 0; for(int i=1;i<=n;i++){ res+=abs(b[mid]-b[i]); } printf("%lld\n",res); } return 0; }