#include <bits/stdc++.h> using namespace std; const int MAXN = 5 * 1e5 + 7; int x; int tab[MAXN]; int main(){ ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> x; tab[x]++; } vector < int > V; for(int i = 1; i <= n; i++){ if(tab[i] != 0){ V.push_back(tab[i]); } } sort(V.begin(), V.end()); deque <int > DQ; for(int i = 0; i < V.size(); i++){ DQ.push_back(V[i]); } int ans = 0; int ile_do_zdjecia = 0; while(DQ.size()){ if(ile_do_zdjecia == 0){ ans++; ile_do_zdjecia = DQ.back() - 1; V.pop_back(); DQ.pop_back(); continue; } if(DQ.front() <= ile_do_zdjecia){ ile_do_zdjecia -= DQ.front(); DQ.pop_front(); } else{ DQ.front() -= ile_do_zdjecia; ile_do_zdjecia = 0; } } cout << ans << 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <bits/stdc++.h> using namespace std; const int MAXN = 5 * 1e5 + 7; int x; int tab[MAXN]; int main(){ ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> x; tab[x]++; } vector < int > V; for(int i = 1; i <= n; i++){ if(tab[i] != 0){ V.push_back(tab[i]); } } sort(V.begin(), V.end()); deque <int > DQ; for(int i = 0; i < V.size(); i++){ DQ.push_back(V[i]); } int ans = 0; int ile_do_zdjecia = 0; while(DQ.size()){ if(ile_do_zdjecia == 0){ ans++; ile_do_zdjecia = DQ.back() - 1; V.pop_back(); DQ.pop_back(); continue; } if(DQ.front() <= ile_do_zdjecia){ ile_do_zdjecia -= DQ.front(); DQ.pop_front(); } else{ DQ.front() -= ile_do_zdjecia; ile_do_zdjecia = 0; } } cout << ans << endl; return 0; } |