题解 | 小红的好数组

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

// 计算把整个已排序数组都变为 b[t] 的 L1 代价（用前缀和 O(1)）
static inline long long cost_all_to_t(const vector<long long>& b,
                                      const vector<long long>& ps, int t) {
    int n = (int)b.size();
    long long left  = 1LL * b[t] * t - (t ? ps[t - 1] : 0LL);
    long long right = (ps[n - 1] - ps[t]) - 1LL * b[t] * (n - 1 - t);
    return left + right;
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    vector<long long> ps(n);
    ps[0] = a[0];
    for (int i = 1; i < n; ++i) ps[i] = ps[i - 1] + a[i];
    // 删去一个下标后，长度 m = n-1 的中位数位置 j = m/2（0-based）
    int j = (n - 1) / 2;
    int tL = j;
    int tR = min(n - 1, j + 1);
    long long allL = cost_all_to_t(a, ps, tL); // 全体变成 a[tL] 的代价
    long long allR = cost_all_to_t(a, ps, tR); // 全体变成 a[tR] 的代价
    long long ans = (1LL << 62);
    for (int i = 0; i < n; ++i) {
        if (i <= j) {
            // 删 i 后中位数在原数组位置 tR
            long long cand = allR - llabs(a[i] - a[tR]);
            if (a[i] == a[tR]) cand += 1; // 需要把“不同的那个”挪开 1
            ans = min(ans, cand);
        } else {
            // 删 i 后中位数在原数组位置 tL
            long long cand = allL - llabs(a[i] - a[tL]);
            if (a[i] == a[tL]) cand += 1;
            ans = min(ans, cand);
        }
    }
    cout << ans << '\n';
    return 0;
}