1045: [HAOI2008] 糖果传递 - #include <Seter> - using namespace Orz;

1045: [HAOI2008] 糖果传递

Seter posted @ 2012年1月13日 13:17 in BZOJ with tags HAOI , 3504 阅读

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
189027	Seter	1045	Accepted	14428 kb	304 ms	C/Edit	851 B	2012-01-13 12:45:53

555……现在我只能做做傻题了，好桑心……

假设平均数是x，且a1给an了k个（k<0说明是an给a1了-k个），那么总代价就可以算出来：

令bi=sum(a1..i)-ix，则总代价=sum|bi-k|。易知k为中位数时此值最小。问题转化为求中位数……或者直接qsort排序也行。

然后我苦逼地改我的快速k大……最后发现是pi!=p||pj!=p而不是pi!=p&&pj!=p……这里当时还想了半天……我不会快排了T^T

1045
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28	`#include <stdio.h>` `#include <stdlib.h>` `int` `n,a[1000000],z;` `char` `str[10000000],p=str;` `long` `long` `avr,sum;` `inline` `getint(){` `int` `re=0;` `while(p<'0'\|\|p>'9')p++;` `while(p>='0'&&p<='9')re=re10+p++-48;` `return` `re;` `}void` `solve(a,j,k)inta,j,k;{` `int` `p=j>>1,pi=0,pj=j-1,t;` `while(pi!=p\|\|pj!=p){` `while(a[pi]<=a[p]&&pi<p)pi++;` `if(pi!=p){t=a[p];a[p]=a[pi];a[p=pi]=t;}` `while(a[pj]>=a[p]&&pj>p)pj--;` `if(pj!=p){t=a[p];a[p]=a[pj];a[p=pj]=t;}` `}if(p>k)solve(a,p,k);` `else` `if(p<k)solve(a+p+1,j-p-1,k-p-1);` `}main(){` `int` `i=-1;fread(p,1,10000000,stdin);` `for(n=getint();++i!=n;)avr+=a[i]=getint();` `avr/=n;` `for(i=-1;++i!=n;a[i]=sum-a[i]+avr)sum+=a[i]-avr;` `sum=0;solve(a,n,n>>1);z=a[n>>1];` `for(i=-1;++i!=n;)sum+=abs(z-a[i]);` `return` `printf("%lld\n",sum),0;` `}`

By Seter