优化数组元素频率的最小代价 - C++ 代码实现

一种比较直观的思路是，统计数组中每个数字出现的次数，然后计算出每个数字需要增加或减少多少个，再按照代价从小到大排序，依次更改数字直到所有数字出现次数相等。具体实现如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt[10] = {0}; // 统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int avg = n / 10; // 每个数字需要出现的次数
    vector<pair<int, int>> v; // 记录需要更改的数字和代价
    for (int i = 0; i < 10; i++) {
        if (cnt[i] > avg) { // 数字出现次数过多，需要减少
            v.push_back(make_pair(i, cnt[i] - avg));
        } else if (cnt[i] < avg) { // 数字出现次数过少，需要增加
            v.push_back(make_pair(i, avg - cnt[i]));
        }
    }
    sort(v.begin(), v.end(), [](pair<int, int>& a, pair<int, int>& b) { // 按照代价从小到大排序
        return a.second < b.second;
    });
    int ans = 0;
    for (auto p : v) {
        ans += p.second * p.first;
    }
    cout << ans << endl;
    return 0;
}

时间复杂度为 O(10log10)，即 O(1)。