小核桃有 nn 个数字，他可以使用魔法将数字的大小改变。假设他的法力值是 x(1 \leq x \leq 10^{9})x(1≤x≤10 9 )，那么对于每个数字而言，他都可以将这个数字增加或者减少 1 \sim x1∼x，修改数字不消耗法力值。 具体来说，如果一个数字为 2，小核桃的法力值为 3，那么他可以将这个数字减少 1 \sim 31∼3，或者增加 1 \sim 31∼3，即这个数字可能会变为 -1,0,1,3,4,5−1,0,1,3,4,5。当然，小核桃也可以不使用法力，使得这个数字保持不变。 小核桃想要把所有数字变成一样的，害怕法力值太高反噬身体，所以他想知道最低需要多少法力值可以将这些数字变成一样。C++

这是一个典型的贪心问题，我们可以先求出这 nn 个数字的中位数，然后把所有数字变成中位数即可。因为如果一个数字比中位数小 kk，那么它变成中位数需要增加 kk，另外一个数字变成中位数需要减少 kk，总共需要增加减少 2k2k，而中位数比它们都要小，所以我们可以只考虑增加操作，即把小的数变成中位数。因为中位数是中间的数，所以我们只需要把所有数字排序后找到中间的那个数即可。时间复杂度 O(n\log n)O(nlogn)。

C++ 代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    int mid = a[n / 2], res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - mid);
    cout << res << endl;
    return 0;
}