【luogu CF1427F】Boring Card Game（贪心）（性质）

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，你需要进行若干次操作，每次操作可以选择一个数 $a_i$，并将其替换为 $a_i-1$ 或 $a_i+1$。你需要使得序列中的所有数都相等，求最少需要进行多少次操作。

$n\leq 10^5$，$|a_i|\leq 10^9$。

解题思路

首先考虑一个简单的问题：给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，你需要进行若干次操作，每次操作可以选择一个数 $a_i$，并将其替换为 $a_i-1$ 或 $a_i+1$。你需要使得序列中的所有数都相等，求最少需要进行多少次操作。

我们可以发现，对于一个数 $x$，如果我们将所有数都变成 $x$，那么需要的操作次数就是 $\sum_{i=1}^n |a_i-x|$。因此，我们可以枚举 $x$，计算出每个 $x$ 对应的操作次数，取最小值即可。

回到原问题，我们可以发现，如果我们将所有数都变成 $\lfloor\frac{\sum_{i=1}^n a_i}{n}\rfloor$，那么需要的操作次数就是 $\sum_{i=1}^n |a_i-\lfloor\frac{\sum_{i=1}^n a_i}{n}\rfloor|$。因此，我们可以先计算出 $\lfloor\frac{\sum_{i=1}^n a_i}{n}\rfloor$，然后再按照上面的方法计算出最小操作次数。

代码实现