#include <bits/stdc++.h> #define st first #define nd second using namespace std; int hist[500100]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=0; i<n; i++) { int a; cin>>a; hist[a]++; } sort(hist, hist + 500050, greater<int>()); int sz=0; while (hist[sz]!=0) { sz++; } int pu = 0, lu = sz-1; int res=sz; while(pu<lu) { while(hist[pu]>1&&pu<lu) { int mi = min(hist[pu]-1, hist[lu]); hist[lu] -= mi; hist[pu] -= mi; if(hist[lu]==0) { lu--; res--; } } pu++; } 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 | #include <bits/stdc++.h> #define st first #define nd second using namespace std; int hist[500100]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=0; i<n; i++) { int a; cin>>a; hist[a]++; } sort(hist, hist + 500050, greater<int>()); int sz=0; while (hist[sz]!=0) { sz++; } int pu = 0, lu = sz-1; int res=sz; while(pu<lu) { while(hist[pu]>1&&pu<lu) { int mi = min(hist[pu]-1, hist[lu]); hist[lu] -= mi; hist[pu] -= mi; if(hist[lu]==0) { lu--; res--; } } pu++; } cout<<res; } |