MENU

洛谷P2512/BZOJ1045/COGS1314/BZOJ1465/洛谷P3156/BZOJ3293/COGS1430/UVa11300/洛谷P4016/COGS741 [HAOI2008]糖果传递/[CQOI2011]分金币/Spreading the Wealth/负载平衡问题

洛谷P2512

BZOJ1045

COGS1314

BZOJ1465

洛谷P3156

BZOJ3293

COGS1430

UVa11300

洛谷P4016

COGS741

求出每个人需要或者多余的数量,转成前缀和,答案为每个数与中位数的距离和。

n倍的经验,n倍的快乐

#include<cstdio>
#include<algorithm>
#include<cstdlib>
int n;
long long a[1000001], f[1000001], sum, ans;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)scanf("%lld", a + i), sum += a[i];
    sum /= n;
    for(int i = 1; i <= n; ++i)f[i] = f[i - 1] + a[i] - sum;
    std::sort(f + 1, f + n + 1);
    for(int i = 1; i <= n; ++i)ans += abs(f[i] - f[(n + 1) / 2]);
    printf("%lld", ans);
}
Leave a Comment

captcha
请输入验证码