BZOJ3293: [Cqoi2011]分金币

2019-11-06 06:12:11

字体：大中小

来源：转载

供稿：网友

经典贪心

设第x人给他右边的人xi个金币，因为最后每个人的金币数ave易知，所以可以得到n个方程： a1+xn-x1=ave a2+x1-x2=ave ….. 设bi=ai-ave 得 x1=xn+b1 x2=x1+b2=xn+b1+b2 …. 设ci=∑ii=1bi $ci=/sum_{i=1}^ibi$ 所以答案就是 ans=∑|xi|=∑|xn+ci| $ans=/sum|xi|=/sum|xn+ci|$ 将所有ci取反，得ans=∑|xn−ci| $ans=/sum|xn-ci|$ ，当xn为这些数的中位数时ans有最小值

code：

#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;const int maxn = 110000;int a[maxn],n;ll as[maxn];int main(){ scanf("%d",&n); ll s=0; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); a[i]=x; s+=x; } s/=(ll)n; ll ave=s; s=0; for(int i=1;i<n;i++) { s+=a[i]-ave; as[i]=-s; } as[n]=0; sort(as+1,as+n+1); ll ans; if(n&1) ans=as[n/2+1]; else ans=(as[n/2]+as[n/2+1])/2; ll ret=0; for(int i=1;i<=n;i++) ret+=abs(ans-as[i]); PRintf("%lld/n",ret); return 0;}

上一篇：分享Window服务项目脚手架

下一篇：1123.Is It a Complete AVL Tree (30)