BZOJ 1045: [HAOI2008] 糖果传递

starli posted @ 2016年2月08日 17:02 in 乱搞? , 207 阅读
设第i个小朋友从左边拿bi个 平均数为t
ai+bi-b(i+1)=t 不妨设b1=k
bn    =  k+t-an
bn-1  =  k+2t-an-a(n-1)
bn-2  =  k+3t-an-a(n-1)-a(n-2)
...
费用为sum(|bi|) 似乎3分就可以了?
不 还可以更快 绝对值的式子怎么化简呢?
考虑数形结合 那么就转化成了:k到各个数字的距离 于是就是中位数了!
然而这个复杂度还是nlogn的……
 
这道题好像刘汝佳的训练指南上第一章有讲到过,也可以参考那个的解答
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
LL n,a[N],t,tmp[N],k,ans;
void read(LL &x){char c;while((c=getchar())<'0'||c>'9');x=c-'0';while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';}
int main(){
	//freopen("1045.in","r",stdin);freopen("1045.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
	t=a[n]/n;
	tmp[n]=0;
	for(int i=1;i<n;i++) tmp[i]=i*t-a[n]+a[n-i];
	std::sort(tmp+1,tmp+n+1);
	k=tmp[(n+1)>>1];
	for(int i=1;i<=n;i++) ans+=abs(k-tmp[i]);
	printf("%lld",ans);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter