糖果传递

_zjz

2018-08-15 20:11:53

Solution

## 题目描述: 有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; } ```