题目：[HAOI2008]糖果传递

光看题几乎没有思路，但是显然到最后每个人手中一定有 d=s/n个糖果（s为所有人糖果总和），不妨设2号给1号x2个糖果，3号给2号x3个.....1号给n号x1个，那么显然a1-x1+x2=d,a2-x2+x3=d

这不就是个n元n次方程组，但是不是，最后一个方程组可以由前面的方程组推出来，因此我们试着用x1表示其他的x，x2=d+x1-a1=x1-c1 (c1=a1-d),x3=d+x2-a2=d+d+x1-a1-a2=x1+d-c1-a2=x1-c2(c2=c1+a2-d)....

我们希望abs(x1)+abs(x2)....+abs(xn)最小，也就是abs(x1)+abs(x1-c1)+abs(x1-c2)....最小，怎么办呢，不难联想绝对值几何意义，先把零点（c）排序，然后中间（奇）的或中间部分（偶）一定是使得上述式子最小的点。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#define int long long

const int N=1e6+5;

using namespace std;

int n,a[N],c[N],m,s;

signed main()

{

	scanf("%lld",&n);

	for(int i=1;i<=n;i++)

	    scanf("%lld",&a[i]),m+=a[i];

	m/=n;

	for(int i=1;i<n;i++)

	    c[i]=c[i-1]+a[i]-m;

	sort(c,c+n);

	int pos=c[n/2],ret=0;

	for(int i=0;i<n;i++)

	    ret+=abs(c[i]-pos);

	printf("%lld\n",ret);

	return 0;

}

巴特西

2022春每日一题：Day 22

题目：[HAOI2008]糖果传递

最新文章

热门文章