[HAOI2008]糖果传递 结论题

题目描述

暴力的做法比较显然，有\(30\)分，这里就不再赘述了。

推一波式子：先考虑一条链的情况，\(a[i]\)为原数组，\(b[i]\)为\(a[i]\)每项分别减掉平均数的数组，\(sum1[i],sum2[i]\)分别为\(a[i],b[i]\)的前缀和数组，\(ave\)为平均数。则\(ans\)可表示为\(\sum\limits_{i=1}^{n}|i*ave-sum1[i]|\)，再化简得到\(\sum\limits_{i=1}^{n}|sum2[i]|\)。然后是环形的情况，断环为链的位置不同，会变化的量就是前缀和数组。假设断环的位置为\(p\)，则前缀和变为\(sum2[k+1]-sum2[k],sum2[k+2]-sum2[k]...\)，减掉重复部分就是\(sum2[k]-sum2[1],sum2[k]-sum2[2]...\)，所以答案就是\(\sum\limits_{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;

}