Problem - 2057B - Codeforces
这个题目著需要知道有多少不重复的数字,然后再把数量最少的数字进行变更为其它数量多的数字,直到剩余一个数字。
当然做这个我第一反应是使用unordered_map来进行储存数字和数字的数量,然后再排序。
后来翻题解的时候,看到大佬的代码。顿悟了,可以不用知道哪个数的数量最少,只需要直到所有不重复数字的数量,然后再进行排序就可以了。
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}// 对所有的数,进行排序。然后再进行计数。std::sort(a.begin(), a.end());std::vector<int> cnt = {1}; // 初始化 cnt 向量for (int i = 1; i < n; i++) {if (a[i] == a[i - 1]) { // 如果当前元素与前一个元素相同,增加计数cnt.back()++; } else {cnt.emplace_back(1); // 如果当前元素与前一个元素不同,添加新的计数}}// 对计数进行排序,然后进行减法。std::sort(cnt.begin(), cnt.end());int m = cnt.size();for (int i = 0; i < m - 1; i++) {if (cnt[i] > k) {std::cout << m - i << "\n";return;}k -= cnt[i];}std::cout << 1 << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}
}