题目描述
有 n 个小朋友坐成一圈,每人有 a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n,表示小朋友的个数。
接下来 n 行,每行一个整数 a[i],表示第 i 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数,表示最小代价。
数据范围
1≤n≤1000000,
0≤a[i]≤2×109,
数据保证一定有解。
输入样例:
4
1
2
5
4
输出样例:
4
第一次做不会推导 听完后太妙了QWQ
(没用latex 回头改)
公式推导
- 假定每个小伙伴分别有a1 a2 a3 a4 … an个糖果,a2传递给a1 x1个糖果 a3传递给a2 x2个糖果,以此类推
如果x是负数则是反向传递。由此我们要求得结果就是 min{|x1|+|x2|+|x3|+…+|xn|}。 - 同时注意到一些性质。 每个小伙伴在给出和得到糖果后为平均糖果数aa
已知数和未知数分离,移项后得到
x1-xn+a1=aa --> xn-x1=a1-aa
x2-x1+a2=aa --> x2-x1=a2-aa
.
.
.
--> xn-1-xn-2=an-1-aa
- 通过相邻两项的关系,可以表示出xi
xn = | x1 - (aa - an) |
xn-1 = | x1 - (2*aa - an - an-1) |
.
.
.
x2 = | x1 - ((n-1)*aa - an - an-1 - ... -a2) |
x1 = x1
- 由此带绝对值可以看成 x1到 x1减去的那一项的的距离,由此减去的那一大项可以看成坐标上的点,求x1到这些点距离和的最小值
- 求解过程参考 货仓选址
参考文献
y总辅导课
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
typedef long long LL;
int n;
LL a[N],b[N];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)cin >> a[i],a[i]+=a[i-1];
LL ave=a[n]/n;
for(int i=1;i<=n;i++)
b[i]=(n-i+1)*ave-(a[n]-a[i-1]);
sort(b+1,b+1+n);
LL res=0;
for(int i=1;i<=n/2;i++)res+=(b[n-i+1]-b[i]);
cout<<res<<endl;
return 0;
}