[bzoj1045] [洛谷P2512] [HAOI2008] 糖果传递

Description###

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

Input###

第一行一个正整数nn<=1'000'000，表示小朋友的个数．

接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．

Output###

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

Sample Input###

Sample Output###

想法##

设第$i$个小朋友从他左边小朋友那里得到 $l_i$ 个糖果，向他右边的小朋友传递 $r_i$ 个糖果

（$l_i$ 与 $r_i$ 都可以为负数）

显然 $l_i=r_{i-1}$ ,特殊地 $l_1=r_n$

设$p$为最终每个小朋友手中的糖果数

则有 $l_i+a_i-r_i=p$ , 即 $ r_i=l_i+(a_i-p) $

而我们又有 $l_i=r_{i-1}$

一直递归下去有 $ r_i=l_1+(a_1-p)+(a_2-p)+(a_3-p)+…+(a_i-p) $

最终答案为 $|r_1|+|r_2|+…+|r_n|$

我们可以记下 $a_i-p$ 的前缀和为 $sum_i$

那么 $ans=|l_1+sum_1|+|l_1+sum_2|+…+|l_1+sum_n|$

绝对值是个美妙的东西，$|l_1+sum_i|$ 可想为数轴上 $-l_i$ 与 $sum_i$ 的距离

那么$ans$的最小值在 $-l_1$ 取 $sum_i$ 中位数时取到

求出$sum_i$及其中位数后计算即可。

代码##

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1000005;

int a[N];

ll sum[N],p;

int n;

int main()

{

    scanf("%d",&n);

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

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

        p+=a[i];

    }

    p=p/n;

    sum[0]=0;

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

        sum[i]=sum[i-1]+a[i]-p;

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

    ll l=sum[n/2+1],ans=0; //注意：中位数为n/2+1而不是n/2

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

        ans+=abs(sum[i]-l);

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

    return 0;

}

巴特西