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

题目描述

小美拿到了一个数组，她每次可以进行如下操作：选择两个元素，一个加 1，另一个减 1。小美希望若干次操作后，众数的出现次数尽可能多。你能帮她求出最小的操作次数吗？
众数定义：在一组数据中，出现次数最多的数据（可能有多个）。

本题是考察贪心与数学分析的题，难度中等。

核心思路

核心观察

1. 操作守恒性：每次操作不改变数组总和 ，只重分配数值。
2. 最大众数频次：
   • 若 ，可使所有 个元素等于 ，频次为 。
   • 否则，最大频次为 （因无法使所有元素相等，但可使任意 个元素相等）。
3. 最优目标值：对于 个元素，使其等于整数 的最小操作次数在 或 时取得（ 为剩余元素的平均值）。
4. 离群点移除：为最小化操作次数，应移除最大值或最小值（使剩余元素更集中）。

算法步骤

1. 计算数组总和 。
2. 情况一：若 ：
   • 目标值 。
   • 操作次数 = 所有大于 的元素与 的差值之和。
3. 情况二：若 ：
   • 分别尝试移除最大值和最小值。
   • 对每种移除方案：
     • 计算剩余和 。
     • 计算 和余数 。
     • 尝试目标值 和 ：
       • 的操作次数 = surplus（大于 的部分）。
       • 的操作次数 = surplus + （补偿总和缺口）。
   • 取所有方案的最小操作次数。

正确性分析

• 情况一：当 可被 整除时，所有元素等于 是唯一能达到频次 的方案，且操作次数最小（由守恒性保证）。
• 情况二：
  • 移除最大值/最小值确保剩余元素范围最小，降低调整成本。
  • 尝试 和 覆盖了使绝对偏差和最小的两个候选整数（因绝对偏差和是凸函数）。
  • 补偿项 正确处理了目标总和与原始剩余和的差异（操作次数需包含此缺口）。

复杂度分析

• 时间复杂度：
  • 计算总和、找最值下标、计算操作次数均为单次遍历。
• 空间复杂度：
  • 存储输入数组，其余变量为常数空间。

参考代码

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

// 计算 a[i] > val 的部分(surplus)
long long cnt(const vector<long long>& a, long long val, int index) {
    long long ans = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        if (i == index) continue;
        if (a[i] > val) {
            ans += a[i] - val;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    // 找最大值和最小值的下标
    int indexmax = 0, indexmin = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[indexmax]) indexmax = i;
        if (a[i] < a[indexmin]) indexmin = i;
    }

    long long ans = 0;

    if (sum % n == 0) {
        ans = cnt(a, sum / n, -1);
    } else {
        // 尝试移除最大值
        long long sum1 = sum - a[indexmax];
        long long p1 = sum1 / (n - 1);
        long long k1 = sum1 % (n - 1);
        long long cost1_option1 = cnt(a, p1, indexmax);
        long long cost1_option2 = cnt(a, p1 + 1, indexmax) + (n - 1 - k1);
        long long cost1 = min(cost1_option1, cost1_option2);

        // 尝试移除最小值
        long long sum2 = sum - a[indexmin];
        long long p2 = sum2 / (n - 1);
        long long k2 = sum2 % (n - 1);
        long long cost2_option1 = cnt(a, p2, indexmin);
        long long cost2_option2 = cnt(a, p2 + 1, indexmin) + (n - 1 - k2);
        long long cost2 = min(cost2_option1, cost2_option2);

        ans = min(cost1, cost2);
    }

    cout << ans << '\n';
    return 0;
}