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

1. 问题建模

1.1 问题本质

该问题包含两个层级的优化目标，需按优先级依次满足：

1. 第一优先级：最大化众数的出现次数 。
2. 第二优先级：在满足最大 的前提下，最小化操作次数。

1.2 操作的不变量（Invariant）

题目中定义的操作是“一个数加 1，另一个数减 1”。这是一个经典的零和博弈操作模型。

• 总和不变性：无论进行多少次操作，数组的总和 始终保持不变。
• 流的概念：操作的本质是将数值从数组的一个位置“流动”到另一个位置。将数组状态 变为 （前提是总和相等）所需的最小操作次数为： 这等同于计算两个状态向量之间的曼哈顿距离的一半。

1.3 众数频率的可行性分析

我们需要判断众数最多能出现多少次。

• 全员相等 ()：若要让所有 个元素都变为同一个数 ，则必须满足 。
  • 这意味着，当且仅当总和 能被 整除（即 ）时，我们才能使众数出现 次。此时的目标值固定为 。
• 全员减一 ()：若无法全员相等，我们总是可以通过操作让 个元素相等。由于我们只需要 个元素变为 ，剩余的那个元素可以吸收或提供所有的“余数”或“差值”，从而保持总和不变。
  • 因为 原本就没有上限和下限（题目虽给正整数，但中间状态通常允许暂时的非正分布，且通常存在一个解使得其余数足够大保持为正），只要 足够大，通常总能找到一个 的解。根据题意示例，如果 不能整除 ，最大众数次数即为 。

2. 算法: 贪心策略结合数学推导

基于上述分析，算法分为两个互斥的分支：

情况 A：总和 能被 整除

此时众数出现次数的最大可能值为 。

• 目标值：。
• 策略：我们将数组中所有元素都变为 。
• 代价计算：计算 。

情况 B：总和 不能被 整除

此时众数出现次数的最大可能值为 。我们需要在数组中选出 个元素，将它们变为某个数 ，并让剩下的 1 个元素承担差值。

• 子数组选择：为了使操作代价最小，选出的 个元素在数值上应该尽可能接近。因此，我们首先对数组进行排序。排序后，最密集的 个元素必然是连续的子数组。此时只有两种选择：

  1. 选择前 个元素（丢弃最大值 ）。
  2. 选择后 个元素（丢弃最小值 ）。

• 目标值 的确定： 对于选定的子集（设大小为 ，和为 ），我们需要将它们变为 。此时剩余的一个元素 变为 。总代价函数为： 实际上，利用不变量原理，代价简化为“子集变成 所需的内部移动”加上“子集与外部的净流量交换”。

  这是一个凸函数优化问题。最优的 通常位于子集的中位数或平均值附近。

  • 算法只需在选定子集的中位数、平均数（取整）附近进行极少量的枚举（例如检查3个候选值），取计算出的最小代价即可。

3. 代码实现

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

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

    int n;
    if (!(cin >> n)) return 0;

    vector<ll> a(n);
    map<ll, int> counts;
    int k_current = 0;
    ll S = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        S += a[i];
        counts[a[i]]++;
        k_current = max(k_current, counts[a[i]]);
    }

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    int k_target = (S % n == 0) ? n : n - 1;

    if (k_current >= k_target) {
        cout << 0 << endl;
        return 0;
    }

    if (k_target == n) {
        ll avg = S / n;
        ll diff = 0;
        for (ll x : a) diff += abs(x - avg);
        cout << diff / 2 << endl;
    } else {
        sort(a.begin(), a.end());
        ll ans = numeric_limits<ll>::max();

        auto eval = [&](int start, int end, ll excluded) {
            vector<ll> candidates;

            ll sub_sum = S - excluded;
            candidates.push_back(sub_sum / (n - 1));
            candidates.push_back(sub_sum / (n - 1) + 1);

            for (ll x : candidates) {
                ll remainder = S - (n - 1) * x;
                ll cur = abs(excluded - remainder);
                for (int i = start; i <= end; i++) {
                    cur += abs(a[i] - x);
                }
                ans = min(ans, cur / 2);
            }
        };

        eval(1, n - 1, a[0]);
        eval(0, n - 2, a[n - 1]);

        cout << ans << endl;
    }

    return 0;
}