AcWing 122. 糖果传递
原题链接
中等
作者:
cisdes
,
2022-04-02 11:01:32
,
所有人可见
,
阅读 183
//首先每个小朋友得到的糖果数一样,都是avg (sum / n)
//我们假设第一个人给出x1收到x2
//a[1] - x1 + x2 = avg;
//a[2] - x2 + x1 = avg;
//....
//a[n] - xn + x1 = avg;
//我们将这些等式转换成xn - x1 ;
//x2 - x1 = -a[1] + avg;
//x3 - x1 = -a[1]-a[2] + avg;
//x4 - x1 = avg - a[1] - a[2] - a[3]
//因此要让移动次数最小即使得上述的和最小
//|xn - x1| + |xn-1 - x1| + ... |x2 - x1|即绝对值不等式
//构造出数组C,c[i] = c[i-1] -avg + a[i];
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a[1001000],c[1001000];
LL sum,res,avg;
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>a[i];
sum += a[i];
}
avg = sum / n;
for(int i = 1;i < n;i++)
{
c[i] = c[i-1] - avg + a[i-1];
}
sort(c,c+n);
int len = c[n / 2];
for(int i = 0;i < n;i++)
{
res += abs(c[i] - len);
}
cout<<res;
}