bzoj1465 bzoj1045: [HAOI2008] 糖果传递&&bzoj3293: [Cqoi2011]分金币

一道神奇的题。。看到做法是排序我的心是绝望的。。

首先我们可以先求出每个小朋友应该得到的糖果数，就是平均值，然后ave-a[i]就代表要从其他小朋友那得到多少个糖果（如果是负数就是要送出糖果）然后求前缀和，往前面延伸，将值想象成数轴上的点，数轴上任意点到其他的值的点的最小距离和就在中位数。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

int a[],p[];

int main()

{

    int n;LL ave=;

    scanf("%d",&n);

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

    {

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

        ave+=a[i];

    }

    ave/=n;

    for(int i=;i<=n;i++)p[i]=p[i-]+ave-a[i];

    sort(p+,p+n+);

    LL ans=;

    for(int i=;i<=n;i++)ans+=abs(p[i]-p[(n+)/]);

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

    return ;

}

巴特西

bzoj1465 bzoj1045: [HAOI2008] 糖果传递&&bzoj3293: [Cqoi2011]分金币

最新文章

热门文章