「一本通 1.1 练习 6」糖果传递

解题报告 贪心

---

题目描述

https://loj.ac/problem/10010

原题来自：HAOI 2008
有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 1 。求使所有人获得均等糖果的最小代价。
对于 100% 的数据，$n \leq 10^6$ ，保证答案可以用 64 位有符号整数存储。

题解

设 $x_i$ 表示第 $i$ 个人向第 $i-1$ 个人传递 $x_i$ 颗糖果，$ave$ 为 $a_i$ 的平均数。
那么显然对于 $1 \leq i < n$，都有 $a_i - x_i + x_{i+1} = ave$，移项得 $x_i - x_{i+1} = a_i - ave$

那么可以列出以下 $n-1$ 个式子：

$$x_1 - x_2 = a_1 - ave \\ x_2 - x_3 = a_2 - ave \\ x_3 - x_4 = a_3 - ave \\ \cdots \\ x_{n-1} - x_n = a_{n-1} - ave\\ $$

把后 $n-1$ 个式子相加，可得：

$$x_1 - x_n = \Sigma_{i=1}^{n-1} a_i - (n-1)ave$$

即

$$x_1 = \Sigma_{i=1}^{n-1} a_i - (n-1)ave + x_n$$

可以看到，等式右边是 $x_n$ 加上一个常数 $t_1$，所以

$$x_1 = x_n + t_1$$

同理把后 $n-2、n-3、n-4、\cdots 1$ 个式子相加，可以得到

$$x_1 = x_n + t_1 \\ x_2 = x_n + t_2 \\ \cdots \\ x_{n-1} = x_n + t_{n-1}$$

而题目求的是最小化 $|x1|+|x2|+|x3|+\cdots+|xn|$，即

$$|x_n+t_1|+|x_n+t_2|+\cdots+|x_{n-1}+t_{n-1}|+|x_n+t_n| \quad (t_n=0).$$

因为其中 $t_i$ 均为常数，所以当 $x_n$ 取 $t_i$ 中位数时该式有最小值。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000007;
int n, a[MAXN];
ll t[MAXN], ans, sum, ave;
inline void read(int &x){
    int val=0; bool f=false; char ch=getchar();
    while ((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
    if (ch=='-') f=true,ch=getchar();
    while (ch>='0'&&ch<='9')val=(val<<3)+(val<<1)+ch-'0',ch=getchar();
    x = f ? (-val) : val;
}
int main(){
    read(n);
    for (int i = 1; i <= n; ++i){
        read(a[i]);
        sum = sum + a[i];
    }
    ave = sum / n;
    t[n] = 0;
    for (int i = n - 1; i >= 1; --i)
        t[i] = t[i+1] + a[i] - ave;
    for (int i = 1; i <= n; ++i)    
        t[i] = -t[i];
    sort(t + 1, t + 1 + n);
    ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = ans + abs(t[(n+1)/2] - t[i]);
    printf("%lld\n", ans);
    return 0;
}