【BZOJ 1045】 [HAOI2008] 糖果传递

在这里输入题意

【题解】

思路来自hzwer..
设xi表示第i个人往左传递了xi个糖果。
(如果小于0表示旁边的人给他了糖果。
则ans=∑|xi|
最后所有人的糖果数都变成sum/n->avg
则
a1-x1+x2 = avg
a2-x2+x3= avg
...

然后可以用avg和x1来表示所有的x2...xn

比如

x2 = x1-(avg-a1)

x3 = x1-(2avg-a1-a2)

....

会发现x1右边的式子都是常量。

且都是x1-ci的形式

那么就相当于有n个点。

然后现在让你选择一个点x1.

使得∑|x1-ci|最小。

显然选择所有这些点里面的中位数就好。

(即ci的中位数

(ci可以观察形式,用递推的方法得到

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define ls l,mid,rt<<1

#define rs mid+1,r,rt<<1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int N = 1e6;

int n;

int a[N+10],c[N+10];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

    scanf("%d",&n);

    rep1(i,1,n)

        scanf("%d",&a[i]);

    LL sum = 0;

    rep1(i,1,n) sum+=a[i];

    sum/=n;

    c[1] = sum-a[1];

    rep1(i,2,n-1) c[i] = c[i-1] + sum-a[i];

    c[n] = 0;

    sort(c+1,c+1+n);

    LL x1 = c[n/2+1];

    sum = 0;

    rep1(i,1,n)

        sum+=abs(x1-c[i]);

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

	return 0;

}

巴特西

【BZOJ 1045】 [HAOI2008] 糖果传递

最新文章

热门文章