#include<bits/stdc++.h> using namespace std; int tab[500005]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a; cin>>a; for(int x = 0; x < a; x++) { int c; cin>>c; tab[c]++; } vector<int> v; for(int x = 0; x <= 500001; x++) if(tab[x] >= 1) v.push_back(tab[x]); sort(v.begin(), v.end()); reverse(v.begin(), v.end()); int res = 0, act = (int)v.size() - 1; for(int x = 0;x < v.size(); x++) { res++; int pom = v[x] - 1; while(act > x) { if(pom >= v[act]) { pom -= v[act]; act--; } else { v[act] -= pom; break; } } if(x == act) break; } cout<<res; 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 | #include<bits/stdc++.h> using namespace std; int tab[500005]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a; cin>>a; for(int x = 0; x < a; x++) { int c; cin>>c; tab[c]++; } vector<int> v; for(int x = 0; x <= 500001; x++) if(tab[x] >= 1) v.push_back(tab[x]); sort(v.begin(), v.end()); reverse(v.begin(), v.end()); int res = 0, act = (int)v.size() - 1; for(int x = 0;x < v.size(); x++) { res++; int pom = v[x] - 1; while(act > x) { if(pom >= v[act]) { pom -= v[act]; act--; } else { v[act] -= pom; break; } } if(x == act) break; } cout<<res; return 0; } |