BZOJ1045 [HAOI2008] 糖果传递 【数学】

tonyfang posted @ 2016年5月06日 22:38 in BZOJ with tags C++ OI , 282 阅读

题解:

跟均分纸牌差不多

 

# include <stdio.h>
# include <algorithm>

using namespace std;

int n, a[10000010], p[10000010];
long long sum;
/*
p[i] = p[i-1] + sum - a[i]
p[1] = p[n] + sum - a[1]
p[n] = sum - a[1] - p[1];
sigma (p[1] + p[2] +...+p[n]) 
*/

int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%d", &a[i]), sum+=a[i];
	sum=sum/n;
	for (int i=2; i<=n; ++i) p[i] = p[i-1] + sum - a[i];
	sort(p+1, p+n+1);
	int mid = p[n/2];
	long long ans=0;
	for (int i=1; i<=n; ++i)	
		ans += abs(mid - p[i]);
	printf("%lld\n", ans);

	return 0;
}

登录 *


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