题目描述

关系

02-pages/104-货仓选址

内容

有 $n$ 个小朋友坐成一圈，每人有 $a[i]$ 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 $1$。

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

输入格式

第一行输入一个正整数 $n$，表示小朋友的个数。

接下来 $n$ 行，每行一个整数 $a[i]$，表示第 $i$ 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围

$1\le n\le 1000000$,
$0\le a[i]\le 2\times {10}^9$,
数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

问题分析

最初思路

先求出平均值，因为最后所有人的状态都会变成这个平均值。

不论怎么说，高于平均值的人，总是要将自己的糖果传递的，低于平均值的人，总是需要别人的糖果的。像水一样。

所以，我们只要从左向右遍历，只要当前小朋友的糖果高于平均值，那么就把高于平均值的那一部分传递。

我们只用考虑高于平均值的部分，或者低于平均值的部分就可以了。

对于低于平均值的人，只需要向两边高于它的要，要到平均值后就不要了，到下一个人。贪心的点在于传递的路径要尽可能小。

思路分析

我们假设最终状态的各个人向周围传递的数据为：

那么，最终我们的花费为： $\text{cost}={\displaystyle \mid x_1\mid +\mid x_2\mid +\mid x_3\mid +\cdots +\mid x_{n-1}\mid +\mid x_n\mid }$. 我们要让这个值最小。光有这个条件是不足以得出这个最小值的，所以我们要找约束条件，一个约束条件是所有元素最后的值都为 ${\displaystyle \overline{sum}}$.

所以我们得出以下式子：

我们设：

那么就有如下递推式：

从而：

现在这个问题就转化为 02-pages/104-货仓选址了。我们只需要求出 ${\displaystyle c_n}$ 数组的中位数就解决了问题。

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;

const int N = 1e6 + 10;
int n; 
ll sum, x;
int a[N], c[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {cin >> a[i]; sum += a[i];}
    
    x = sum / n;
    
    for (int i = n; i > 1; i--) {
        c[i] = c[i + 1] + x - a[i];
    }
    
    c[1] = 0;
    
    sort(c + 1, c + n + 1);
    
    ll res = 0;
    for (int i = 1; i <= n; i++) res += abs(c[i] - c[(n + 1) / 2]);
    cout << res;
    return 0;
}