有一个长度为 n 的数组n 是 10 的倍数每个数 ai 都是区间 0 9 中的 整数。小明发现数组里每种数出现的次数不太平均而更改第 i 个数的代价为 bi他想更改若干个数的值使得这 10 种数出现的次数相等都等于 n10 请问 代价和最少为多少。代码

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

#include #include #include 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)。