【P2512】[HAOI2008]糖果传递
Palace
2018-10-08 20:51:31
[走你](https://www.luogu.org/problemnew/show/P2512)
## 思路：
这是个环形的[均分纸牌](https://www.luogu.org/problemnew/show/P1031)。
在这里记录一下zhw的**数学**做法。
我们设$X_i$表示第$i$个人需要给第$i-1$个人的糖果，设最后每人手中都有$ave$块糖，则$ans=\sum_{i=1}^n|X_i|$，那么：
$a_i-X_i+X_{i+1}=ave$
那么，
$a_1-X_1+X_2=ave$ $=>$ $X_2=ave-a_1+X_1$
令$C_1=a_1-ave$
那么，
$X_2=X_1-C_1$
还有，
$a_2-X_2+X_3=ave-a$ $=>$ $X_3=ave+X_2-a_2$ $=>X_3=2×ave-a_1-a_2+X_1$ $=>$ $X_1-C_2$
...
我们发现$C_i=sum_i-ave×i$，我们就得到了求$C_i$的方法，而对于$X_i=X_1-C_{i-1}$。
所以$ans=\sum_{i=1}^n|X_i|=|X_1-0|+|X_2-C_1|+...+|X_n-C_{n-1}|$
根据数学知识，这个式子表示$X_1$到数轴上$C_0$ 到 $C_{n-1}$的点的距离之和，所以$X_1$取中位数时，$ans$最小。
## 代码：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
LL n, ave, ans;
LL a[N], c[N], x[N], cc[N], s[N];
int main() {
scanf( "%lld", &n );
for( LL i = 1; i <= n; ++i ) {
scanf( "%lld", &a[i] );
s[i] = s[i - 1] + a[i];
}
ave = s[n] / n;
for( LL i = 1; i <= n - 1; ++i ) {
c[i] = s[i] - ( ave * i );
cc[i] = c[i];
}
sort( cc + 1, cc + 1 + n - 1 );
x[1] = cc[( n + 1 ) >> 1];
for( LL i = 2; i <= n; ++i )
x[i] = abs( x[1] - c[i - 1] );
x[1] = abs( x[1] );
for( LL i = 1; i <= n; ++i )
ans += x[i];
printf( "%lld\n", ans );
return 0;
}
```