P2512 糖果传递

有趣的思维题

[HAOI2008]糖果传递

题目描述

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

输入格式

小朋友个数 $n$，下面 $n$ 行 $a_i$。

对于 $100\%$ 的数据 $n\le 10^6$。

输出格式

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

题目分析

最终所有小朋友的糖果数量都是平均数，那么假设$x_i$为$i$号小朋友给$i-1$号小朋友糖果的个数，正表示给出，负代表被给。那么对于每一个小朋友，可以列出方程：

$a_i-x_i+x_{i+1}=ave\\ x_{i+1} = x_i+ave-a_i$

带入每一个i可以得到：

$\left\{\begin{array}{c}     x_2 = x_1+ave-a_1 \\     x_3 = x_2+ave-a_2 \\ ...\\     x_n = x_{n-1}+ave-a_n \end{array}\right.$

消元可得：

$\left\{\begin{array}{c}     x_2 = x_1+ave-a_1 \\     x_3 = x_1+2*ave-a_1-a_2 \\ ...\\     x_n = x_1+(n-1)*ave-\sum\limits_{i=1}^{n-1}a_i \end{array}\right.$

题目要求的答案为 $\sum\limits_{i=1}^{n}|x_i|$ 那么就转化为了
$\sum\limits_{i=1}^n|x_1+(i-1)*ave-\sum\limits_{j=1}^ia_j|$
那么问题就转化为了在数轴
$x_1$
到
$i*ave-\sum\limits_{j=1}^ia_j$
这些点的距离之和，根据初中数学就能得知
$x_1$为$i*ave-\sum\limits_{j=1}^ia_j$
的中位数时答案最小，然后就做完啦。

代码

//
// Created by mrx on 2022/9/14.
//
#include <bits/stdc++.h>

using ll = long long;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif
    int n;
    while (std::cin >> n) {
        std::vector<ll> c(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> c[i];
            if (i) c[i] += c[i - 1];
        }
        ll ave = c[n - 1] / n;
        for (int i = 0; i < n; ++i) {
            c[i] = (i + 1) * ave - c[i];
        }

        std::nth_element(c.begin(), c.begin() + n / 2, c.end());
        ll x1 = c[n / 2];
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += std::abs(c[i] - x1);
        }
        std::cout << ans << '\n';
    }
    return 0;
}