DQS DQS

[BZOJ1045] [HAOI2008] 糖果传递 中位数

in 算法,其他read (75) 文章转载请注明来源!

Description

有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input

第一行一个正整数nn<=1'000'000,表示小朋友的个数.
接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数.

Output

求使所有人获得均等糖果的最小代价。

Sample Input

4
1
2
5
4

Sample Output

4

先求平均数,然后减去,再差分,得到一个序列。容易发现其实是求一个长度为2n-1的序列中长度为n的序列加上首项前一项的值的绝对值之和。
(其实写出来比较显然的,相当于从第l个人向后传糖果,最后一个人的传递次数恰好为0。因为之前做了差分,所以要加上前一项)

又由于第n项一定为0,发现破环成链意义不大…相当于取了序列中一个数,其他数都减去它,然后再求绝对值之和。

本来以为是树状数组离散化后暴力维护一下…然后看了其他人的做法:

转化后即求$\sum_{i!=k}abs(a_i-a_k)$。
发现这其实是数轴上给定点集,求一个点使得与给定点集距离和最小问题,$a_k$显然是点集的中位数。

所以求出a数组,然后再累加一遍就行了。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int,int> pii;
typedef long long LL;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

LL a[SZ],c[SZ];
int n;

int main()
{
    n = read();
    LL ave = 0;
    for(int i = 1;i <= n;i ++) a[i] = read(),ave += a[i];
    ave /= n;
    for(int i = 1;i <= n;i ++) c[i] = c[i - 1] + a[i] - ave;
    sort(c + 1,c + 1 + n);
    LL mid = c[(n + 1) >> 1],ans = 0;
    for(int i = 1;i <= n;i ++)
        ans += abs(c[i] - mid);
    printf("%lld\n",ans);
    return 0;
}

//-2 -1 2 1 -2 -1 2 1
//-2 -3 -1 0

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法其他
最后由DQS修改于2017-10-25 01:49
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆