122-糖果传递

#personal/blog #algorithm/greedy #algorithm/math

题目描述

关系

02-pages/104-货仓选址

内容

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

输出样例：

问题分析

最初思路

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

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

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

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

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

思路分析

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

那么，最终我们的花费为： $cost = ∣ x_{1} ∣ + ∣ x_{2} ∣ + ∣ x_{3} ∣ + \dots + ∣ x_{n - 1} ∣ + ∣ x_{n} ∣$ . 我们要让这个值最小。光有这个条件是不足以得出这个最小值的，所以我们要找约束条件，一个约束条件是所有元素最后的值都为 $\overset{―}{s u m}$ .

所以我们得出以下式子：

{\begin{cases} a_{1} - x_{1} + x_{2} = \overset{―}{a v g} \\ a_{2} - x_{2} + x_{3} = \overset{―}{a v g} \\ \dots \\ a_{n - 1} - x_{n - 1} + x_{n} = \overset{―}{a v g} \\ a_{n} - x_{n} + x_{1} = \overset{―}{a v g} \end{cases} ⟹ {\begin{cases} x_{1} - x_{2} = a_{1} - \overset{―}{a v g} \\ x_{2} - x_{3} = a_{2} - \overset{―}{a v g} \\ \dots \\ x_{n - 1} - x_{n} = a_{n - 1} - \overset{―}{a v g} \\ x_{n} - x_{1} = a_{n} - \overset{―}{a v g} \end{cases} ⟹ {\begin{cases} x_{n} = x_{1} - (a_{n} - \overset{―}{a v g}) \\ x_{n - 1} = x_{n} - (a_{n - 1} - \overset{―}{a v g}) = x_{1} - (2 \overset{―}{a v g} - a_{n - 1} - a_{n}) \\ x_{n - 2} = x_{1} - (3 \overset{―}{a v g} - a_{n - 2} - a_{n - 1} - a_{n}) \\ \dots \\ x_{2} = x_{1} - ((n - 1) \overset{―}{a v g} - a_{2} - a_{3} - \dots a_{n}) \\ x_{1} = x_{1} - 0 \end{cases}

我们设：

c_{1} = 0, c_{2} = (n - 1) \overset{―}{a v g} - a_{2} - a_{3} - \dots a_{n}, \dots, c_{n} = a_{n} - \overset{―}{a v g} .

那么就有如下递推式：

c_{i} = c_{i + 1} + \overset{―}{a v g} - a_{i}

从而：

cost =∣ x_{1} - c_{1} ∣ + ∣ x_{2} - c_{2} ∣ + \dots + ∣ x_{1} - c_{n} ∣

现在这个问题就转化为 02-pages/104-货仓选址了。我们只需要求出 $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;
}