题目描述

已知序列$A = (A_1, A_2, … … ,A_N)$, 你可以执行任意次以下操作：

• 选择两个整数$i, j (1 \leq i, j \leq N)$, 令 $A_i$ 减 $1$，同时令 $A_j$ 加 $1$。

寻找使得整个序列中最大值和最小值的差距不超过 $1$ 的最少操作数。

样例

输入：

4
4 7 3 7

输出：

3

思路

题目所给操作不会改变整个序列的和。问题的求解可以分成以下两步：

1. 给定序列B， 求将序列A变成序列B的最小操作数
2. 对于序列B， 其最大值与最小值的差距不大于1， 且和等于A序列的和。找到满足该条件，且使1的结果最小的序列B。

给定序列B， 求将序列A变成序列B的最小操作数

对于一个序列$B = (B_1, B_2, … … ,B_N)$, 令$S = \sum|A_i - B_i|$,则将序列A变成序列B的最小操作数为 $\frac{S}{2}$。
证明：

 每次对Ai/Aj 加1或减1会导致S加1或减1。因此一次操作对S的改变量为[-2, 2]。当S变为0时，序列A完全等于序列B。

 因此最优操作是尽可能地让每次操作对S的改变量都为-2， 由此可得最小操作数为 S/2

对于序列B，其最大值与最小值的差距不大于1， 且和等于A序列的和。找到满足该条件，且使1的结果最小的序列B。

首先，先找到和等于A序列的和，且最大值与最小值的差距不大于1的序列B。
这个序列可由如下计算得到：

$ \sum B_i / N = p$, $ \sum B_i % N = r $, 序列B包含了 $(N - r)$ 个 $p$ 和 $r$ 个 $(p + 1)$ 。

当B确定后，最小操作数取得最小值的情况就很自然了：
将A和B都进行升序排序，此时求得的最小操作数就是全局最小值

C++ Code $O(NlogN)$

 #include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5+10;
int n, a[N];

int main()
{
    cin >> n;
    LL sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        sum += a[i];
    }

    sort(a + 1, a + 1 + n);
    LL p = sum / n, mod = sum % n;

    // (n - mod) * p + mod * (p + 1)

    LL res = 0;
    for(int i = 1; i <= n - mod; ++i)
    {
        res += abs(a[i] - p);
    }

    for(int i = n - mod + 1; i <= n; ++i)
    {
        res += abs(a[i] - p - 1);
    }

    cout << res/2 << endl;
    return 0;
}