BZOJ1045 HAOI2008糖果传递（贪心）

　　显然最后每个小朋友所拥有的糖果数就是糖果数总和的平均数。设该平均数为t。

　　环的问题一般断成链，但这个题似乎没有什么很好的办法在枚举断点的时候快速算出答案（我甚至不知道会不会有断点）

　　于是我们假装把他断开了。假装现在我们已经知道了1号小朋友要给n号小朋友x颗糖果（可以为负）。那么，2给1，3给2，4给3，等等等等，小朋友之间传递的糖果数都被确定了。

　　1号给了n号x颗后，其还剩a₁-x颗，那么2号小朋友就要给1号t-(a₁-x)=x-(a₁-t)颗。

　　把1、2号看成整体，给了n号x颗后，其还剩a₁+a₂-x颗，那么3号小朋友就要给他们x-[(a₁+a₂)-t*2]颗。

　　以此类推，k号小朋友要给k-1号x-[(a₁+a₂+……+a_k-1)-t*(k-1)]颗。

　　我们的目标是使上面所有数的绝对值之和最小。与这个值有关的量里只剩x是变量了。

　　那么什么时候这个值最小？假装这有一个数轴，有一些点是0，a₁-t_，(a1+a2)-t*2，等等等等。

　　我们要找一个点x使得其到这些点的距离之和最小。显然放在最中间，也就是中位数的位置就行了。

　　stl里有个nth_element的黑科技，线性找第k大。

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1000010

int n;

long long a[N],s[N],k,ans=;

int main()

{

    n=read();

    for (int i=;i<=n;i++) s[i]=s[i-]+read();

    k=s[n]/n;

    for (int i=;i<=n;i++) a[i]=s[i-]-k*(i-);

    nth_element(a+,a+(n+>>),a+n+);

    for (int i=;i<=n;i++) ans+=abs(a[i]-a[n+>>]);

    cout<<ans;

    return ;

}

巴特西

BZOJ1045 HAOI2008糖果传递（贪心）

最新文章

热门文章