题解 P3156 【[CQOI2011]分金币】
顾z
2018-08-15 18:58:00
**题目描述**
圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。
**分析:**
设：
每个人最后拥有的金币数为m个,
Ai代表第i个人有的金币数量,
Xi代表i给了上一个人多少金币.
则:
A1-X1+X2=m;
变形——>A1-X1+X2=m ==> X2=m+X1-A1=X1-(A1-m)
A2-X2+X3=m ==> X3=m-A2+X2=2m-A2+X1-A1
所以 可得 X3=X1-(A1-m)-(A2-m)
就这样以此类推
我们可以定义w[n]=sigama(1~n)Ai-m;//这就是前缀和啦！
因此结果就是|X1|+|X1-w1|+....+|X1-wn|
因为要求的是**最小值**,所以就转变为数学问题~~(找中点就好啦~~
-------------------代码--------------------
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cctype>
#define IL inline
#define RI register int
long long n,a[1000008],sum,w[1000008],ans;
//128MB= 33554432个int
// long long =2个int
//所以 我开了 4000032个int ？？？？？
// 33554432
// 4000032
IL void read(long long &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
IL void print(long long x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) print(x/10);
putchar(x%10+'0');
}
IL long long abss(long long x){return x<0 ? -x : x;}
int main()
{
read(n);
for(RI i=1;i<=n;i++)read(a[i]),sum+=a[i];
sum/=n;//每个人应有的 emmmm
for(RI i=1;i<=n;i++)a[i]-=sum;
for(RI i=2;i<=n;i++)w[i]=w[i-1]+a[i];
std::sort(w+1,w+n+1);
long long dis=w[ n%2==1 ? (n+1)>>1 : n>>1];
for(RI i=1;i<=n;i++)
ans+=abss(w[i]-dis);
print(ans);
}
```