[HAOI2008]糖果传递 结论题

题目描述

有(n(n<1000000))个小朋友坐成一圈，每人有(a_i)个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为(1)，求使所有人糖果数相等的最小代价。

暴力的做法比较显然，有(30)分，这里就不再赘述了。
推一波式子：先考虑一条链的情况，(a[i])为原数组，(b[i])为(a[i])每项分别减掉平均数的数组，(sum1[i],sum2[i])分别为(a[i],b[i])的前缀和数组，(ave)为平均数。则(ans)可表示为(sumlimits_{i=1}^{n}|i*ave-sum1[i]|)，再化简得到(sumlimits_{i=1}^{n}|sum2[i]|)。然后是环形的情况，断环为链的位置不同，会变化的量就是前缀和数组。假设断环的位置为(p)，则前缀和变为(sum2[k+1]-sum2[k],sum2[k+2]-sum2[k]...)，减掉重复部分就是(sum2[k]-sum2[1],sum2[k]-sum2[2]...)，所以答案就是(sumlimits_{i=1}^{n}|sum2[k]-sum2[i]|)，结论就是(sum2[k])为中位数时是最优的（证明以后再补吧）。照着式子写代码就好了。

#include <cstdio>
#include <algorithm>

using namespace std;

#define N 1000000

int n;
long long sum[N+5], ave;

int main() {
    scanf("%d", &n);
    long long t, ans = 0;
    for(int i = 1; i <= n; ++i) scanf("%lld", &t), ave += t, sum[i] = sum[i-1]+t;
    ave /= n;
    for(int i = 1; i <= n; ++i) sum[i] -= i*ave;
    nth_element(sum+1, sum+(n+1)/2, sum+n+1);
    for(int i = 1; i <= n; ++i) ans += abs(sum[(n+1)/2]-sum[i]);
    printf("%lld", ans);
    return 0;
}