#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; const ll LINF = 1e18; const int INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vi a(n); vi cnt(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; ++cnt[a[i]]; } sort(cnt.begin(), cnt.end(), greater<int>()); int elements_taken = 0, result = 0; for (int i = 0; i < n && elements_taken < n; ++i) { elements_taken += 2 * cnt[i] - 1; ++result; } cout << result << endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; const ll LINF = 1e18; const int INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vi a(n); vi cnt(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; ++cnt[a[i]]; } sort(cnt.begin(), cnt.end(), greater<int>()); int elements_taken = 0, result = 0; for (int i = 0; i < n && elements_taken < n; ++i) { elements_taken += 2 * cnt[i] - 1; ++result; } cout << result << endl; return 0; } |