题解 P2512 【[HAOI2008]糖果传递】
zylll
2019-03-01 16:09:48
思路：看一眼题目是环形均分纸牌。
我们设$X_i$表示第$i$个人给第$i-1$个人的糖果数。
则最终答案为：
$$ans=\sum_{i=1}^n abs(X[i])$$
特殊的是：$X_1$表示第$1$个人给第$n$个人的糖果数。
设：
$$s=(\sum_{i=1}^n a[i] )/n$$
目标状态下，则：
$i=1$时，$s=a_1-X_1+X_2$
$i=2$时，$s=a_2-X_2+X_3$
$i=3$时，$s=a_3-X_3+X_4$
$......$
$i=n$时，$s=a_n-X_n+X_{n-1}$
化成另一种形式：
$X_2=s-a_1+X_1$
$X_3=s-a_2+X_2$
$X_4=s-a_3+X_3$
$......$
$X_n=s-a_{n-1}+X_{n-1}$
我们使$C_i=a_i-s$，则上面形式可以得到简化，即为：
$X_2=X_1-C_1$
$X_3=X_2-C_2$
$X_4=X_3-C_3$
$......$
$X_n=X_{n-1}-C_{n-1}$
把上面式子中的$C$数组展开，显然发现有关$C$数组运算可以使用前缀和处理。
由此，答案转化成了：
$$ans=\sum_{i=1}^n abs(X_1-C_i)$$
显然:
$$ X_1∈C[i],i∈[1,n] $$
我们希望答案最小，转化为数学意义，则最终问题即为，在一个数轴上选出一个点，使得这个点到其他点的距离和最小，则这个点为所有数字中的中位数，证明在此不多赘述。
代码：
```c
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
typedef long long ll;
static const int MAXN=1000050;
using namespace std;
ll n,sum,s,ans,c[MAXN],a[MAXN];
inline ll read(){
ll x=0;bool sign=false;
char alpha=0;
while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
return sign?-x:x;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
sum+=a[i];
}
s=sum/n;
for(int i=1;i<=n;i++){
c[i]=c[i-1]+a[i]-s;
}
sort(c+1,c+n+1);
for(int i=1;i<=n;i++) ans+=abs(c[i]-c[(n>>1)+1]);
printf("%lld\n",ans);
return 0;
}
```