糖果传递
_zjz
2018-08-15 20:11:53
## 题目描述:
有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
------------
## 解:
最终的局面是每个小朋友的糖果数量相同,即为平均数(ave);
设标号为i的小朋友初始有ai个糖果.
xi表示第i个小朋友给第i-1个小朋友xi个糖果
(x1给xn糖果)
容易发现ans=|x1|+|x2|+|x3|......+|xn|;
对于第1个小朋友
易列出a1-x1+x2=ave
依次类推:
#### 易得:
x1=x1-0;
X2=ave-A1+X1=X1-C1 (C1=A1-ave)
X3=2ave-A1-A2+X1+X2=X1-C2 (C2=A1+A2-X2-2ave)
X4=3ave-A1-A2-A3+X1+X2+X3=X1-C3
(C3=A1+A2+A3-X2-X3-3ave)
其中ci可在O(n)时间内预处理出来.
........
ans=|x1|+|x1-c1|+.....|x1-cn-1|.
几何意义即为x1距0,c1,.....cn-1距离和最小
x1取中位数即可。
#### 为什么x1取中位数最小?
当在中位数偏右的位置,向左移的时候左边的点距该点
距离减少d,贡献为左边的点个数*d,
右边的增加右边的点个数*d.左边同理
发现只有在中间的时候达到最小........
### 详见代码:
```
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype>
typedef long long ll;
using namespace std;
const int N=1000001;
ll a[N],s[N];
inline ll read()
{
ll X=0,w=0;char ch=0;
while(!isdigit(ch))
{
w|=ch=='-';ch=getchar();
}
while(isdigit(ch))
{
X=X*10+ch-'0';ch=getchar();
}
return w?-X:X;
}
int main()
{
// freopen("candy.in","r",stdin);
// freopen("candy.out","w",stdout);
ll n,sum=0;
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
sum+=a[i];
}
int x=sum/n;
for(int i=2;i<=n;i++)
s[i]=s[i-1]+x-a[i];//求ci
sort(s+1,s+n+1);
ll k=s[(n+1)/2];//取中位数
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=abs(k-s[i]);//计算答案
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
```