题解 | #小美的数组操作#

简单考虑一下，众数最多要么就全是同一个数有 $n$ 个，做不到则可以 $n-1$ 个1以及一个 $x$ .

前者是简单的，考虑sum%n==0即可直接判断，并计算即可。

我们来考虑第二种情况，在这种情况下，最终结果将会是 $n-1$ 个 $x$ 和一个 $y~(x\ne y)$ . 记 $S$ 为sum。那么满足

(n-1)x+y=S\\

此时我们不知道哪个值会成为 $y$ ，不妨记为 $a_k$ ，那么最终操作次数就是各个值到最终值距离的一半。为了便于行文，我们忽略这个一半，记代价函数

\begin{align} F(x)&=|a_k-y|+\sum_{i\ne k}|a_i-x|\\ &=|a_k-S+(n-1)x|+\sum_{i\ne k}|a_i-x| \end{align}\\

那么最终答案就是 $\displaystyle \min_{1\le k\le n,~x\in N}F(x)/2$

固定 $k$ ，考虑 $x$ 增加1时， $F(x)$ 的变化：

第一项的变化值为 $\pm (n-1)$ ，第二项中，若有 $p$ 个大于 $x$ 的，那么变化就是 $-p+(n-1-p)=n-1-2p$

我们发现，第二项的增量 $n-1-2p\le n-1$ ，换句话说， $x$ 变换时， $F(x)$ 是增是减完全由第一项决定，因此要让第一项尽可能小，也即 $0\le |a_k-S+(n-1)x|< n-1\\$ 否则就能让x变化，达到这个区间。而这个式子等价于

\begin{align} &-(n-1)<a_k-S+(n-1)x<n-1\\ \Leftrightarrow &\dfrac{S-a_k-(n-1)}{n-1}<x<\dfrac{S-a_k+(n-1)}{n-1}\\ \Leftrightarrow & \dfrac{S-a_k}{n-1}-1 <x<\dfrac{S-a_k}{n-1}+1\\ \Leftrightarrow & \lfloor \dfrac{S-a_k}{n-1}\rfloor\le x \le \lceil\dfrac{S-a_k}{n-1}\rceil \end{align}\\

因此，遍历 $k$ 考虑这两个取值即可。

由于需要遍历 $k$ ，我们希望对 $F(x)$ 的计算能快一点，这很好做到：在求和内插入一项 $a_k$ ，之后只要排序后就可以对 $x$ 两侧值各自处理，用前缀和即可。

$F(x)=|a_k-S+(n-1)x|-|a_k-x|+\sum_{1\le i\le n}|a_i-x|\\$

#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>
using namespace std;

long long solve(int n) {
    if(n==1) return 0;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long sum = accumulate(a.begin(), a.end(), 0LL); // 有点搞，这里要用0LL，直接写0会当int溢出
    if (sum % n == 0) {
        long long ans = 0;
        int target = sum / n;
        for (auto num : a) {
            ans += abs(num - target);
        }
        ans /= 2;
        return ans;
    }

    sort(a.begin(), a.end());
    long long ans = LONG_LONG_MAX;

    vector<long long> presum(n+1, 0);
    for (int i = 1; i <= n; i++) presum[i] = a[i-1] + presum[i - 1];

    for (int i = 0; i < n; i++) {
        long long ak = a[i];

        vector<long long> xVal;
        xVal.push_back((sum - ak) / (n - 1));
        if ((sum - ak) % (n - 1) != 0) xVal.push_back((sum - ak) / (n - 1) + 1);


        for (auto x : xVal) {
            long long fx = llabs(0LL+ ak - sum + (n - 1) * x) - llabs(ak - x);
            long long cnt = lower_bound(a.begin(), a.end(), x) - a.begin();
            fx += cnt * x - presum[cnt];
            fx += presum[n] - presum[cnt] - (n - cnt) * x;
            ans = min(ans, fx);
        }
    }
    return ans/2;;

}


int main() {
    int n;
    cin >> n;
    cout << solve(n);
}
// 64 位输出请用 printf("%lld")