有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
假设当所有人获得均等的糖果的时候:
-
每个人手上的糖果的数量为(ave)
-
第(i)个人初始时的糖果数量为(A_i)
-
第(i)个人给了前一个人(X_i)个糖果(如果(X_i)是负数,代表前一个人实际上的给了第(i)个人(X_i)个糖果)
那么对于每个人,都满足等式
[A_i-X_i+X_{(i+1)\%n}=ave
]
然后可以列出n条等式
[A_0-X_0+X_1=ave\
A_1-X_1+X_2=ave\
...\
A_{n-1}-X_{n-1}+X_0=ave\
]
最终的答案应该是(sum_{i=0}^{n-1}|X_{i}|)
实际上以上的其中一条等式能够由其他的(n-1)条等式得到.
不同的等式只有(n-1)条,未知数有(n)个,不能直接解.
假设(X_0)是已知的值,可以推出所有的(X)的值
[X_1=ave-A_0+X_0=X_0-(A_0-ave)\
X_2=ave-A_1+X_1=X_1-(A_1-ave)=X_0-(A_0-ave)-(A_1-ave)\
...\
X_{n-1}=X_0-sum_{i=0}^{n-2}(A_i-ave)
]
定义(C_k=C_{k-1}-(A_i-ave))
那么(|X_k|=|X_0-C_k|)
如何让(sum_{i=0}^{n-1}|X_{i}|)变得尽量小,
可以发现,(|X_0-C_k|)可以看作是数轴上(X_0)和(C_k)的距离,
把(X_0),(C_1),(C_2),...,(C_{n-1}),都列在一条数轴上,
找到其中的一个点,让这个点到其他所有的点的距离的和最小.
显然,这几个点之中最靠中间的点,就是到其他所有点的距离的和最小的点.
那么这个距离的和就是答案
应该如何假设(X_0)的值?
(X_0)的含义是第(0)个人给第(n-1)个人的糖果的数量.
实际上,从第二个人开始,每人给前一个人(X_i)个糖果,到最后第(n-1)个人手上的糖果数就应该是(ave)了.
所以(X_0)应该是(0).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
static ll n, sum, ave, mid, ans, a[1100100], c[1100100];
int main()
{
scanf("%lld", &n);
for(ll i = 0; i < n; ++i)
{
scanf("%lld", &a[i]);
sum += a[i];
}
ave = sum/n;
c[0] = 0;
for(int i = 1; i < n; ++i)
{
c[i] = c[i-1]+a[i]-ave;
}
sort(c, c+n);
mid = c[n/2];
for(int i = 0; i < n; ++i)
ans += abs(c[i] - mid);
printf("%lld
", ans);
}