#include <bits/stdc++.h> using namespace std; set<int>s; int mapa[500009]; deque<int>dq; int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n, res = 0; cin >> n; for(int i = n; i; --i){ int x; cin >> x; mapa[x]++; s.insert(x); } for(auto i : s){ dq.push_front(mapa[i]); } std::sort(dq.begin(), dq.end(), greater<int>()); while(dq.size()) { int x = dq.front(); dq.pop_front(); if(dq.empty()){ res++; break; } while(dq.size()){ int y = dq.back(); if(x-y > 0){ dq.pop_back(); x-=y; if(dq.empty()){ res++; cout << res; return 0; } } else if(x == y){ dq.pop_back(); dq.push_back(1); res++; break; } else{ res++; break; } } } cout << res; }
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 | #include <bits/stdc++.h> using namespace std; set<int>s; int mapa[500009]; deque<int>dq; int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n, res = 0; cin >> n; for(int i = n; i; --i){ int x; cin >> x; mapa[x]++; s.insert(x); } for(auto i : s){ dq.push_front(mapa[i]); } std::sort(dq.begin(), dq.end(), greater<int>()); while(dq.size()) { int x = dq.front(); dq.pop_front(); if(dq.empty()){ res++; break; } while(dq.size()){ int y = dq.back(); if(x-y > 0){ dq.pop_back(); x-=y; if(dq.empty()){ res++; cout << res; return 0; } } else if(x == y){ dq.pop_back(); dq.push_back(1); res++; break; } else{ res++; break; } } } cout << res; } |