#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; } |
English