题解 P2512 【[HAOI2008]糖果传递】
C20203030
2019-10-21 21:38:22
## 一、题目
[点此看题](https://www.luogu.org/problem/P2512)
## 二、解法
设$x_i$为$i$号给$i-1$号$x_i$颗糖果（如果为负则方向相反），让后我们可以列出下面的式子：
$a_1-x_1+x_2=ave$
$\dots \dots$
$a_i-x_i+x_{i+1}=ave$
发现有$n-1$个方程，$n$个未知数，可以解出关系式（定义$c[i]=\sum_{j=1}^{i} a[j]-ave$）：
$x_i=x_1-c[i-1]$
我们的答案就是$|x_1|+|x_1-c[1]|+...+|x_1-c[n-1]|$
可以发现这就是个小学的邮局问题，取$c$的中位数即可。（说中位数可能有点不严谨，详细操作看代码吧）
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 1000005;
int read()
{
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int n,ave,ans,a[MAXN],s[MAXN];
int _abs(int x)
{
return x>0?x:-x;
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
ave+=a[i];
}
ave/=n;
for(int i=1;i<n;i++)
s[i]=s[i-1]+a[i]-ave;
sort(s+1,s+n);
int x1=s[(n+1)/2],val=_abs(x1);
for(int i=1;i<n;i++)
ans+=_abs(x1-s[i]);
n--;
if(n%2==0) val=min(_abs(s[n/2]),_abs(s[n/2+1]));
printf("%lld\n",ans+val);
}
```