#include<bits/stdc++.h> using namespace std; const int MAX_N = 1e6 + 7; int dane[MAX_N]; vector<int> wyst; int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for(int i = 0; i < n; ++i) { cin >> dane[i]; } sort(dane, dane + n); int w = 1; for(int i = 1; i < n; ++i) { if(dane[i - 1] == dane[i]) w++; else{ wyst.push_back(w); w = 1; } } wyst.push_back(w); sort(wyst.begin(), wyst.end(), greater<int>()); //for(int i : wyst) cout << i << ' '; int k = wyst.size() - 1; int res = 0; int ile = 0; for(int i = 0; i < wyst.size(); ++i) { ile = 0; if(wyst[i] > 0) { res++; while(ile < wyst[i] - 1 && k > i) { if(ile + wyst[k] > wyst[i] - 1) { int add = wyst[i] - 1 - ile; wyst[k] -= add; ile += add; } else { ile += wyst[k]; wyst[k] = 0; k--; } } } } 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 | #include<bits/stdc++.h> using namespace std; const int MAX_N = 1e6 + 7; int dane[MAX_N]; vector<int> wyst; int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for(int i = 0; i < n; ++i) { cin >> dane[i]; } sort(dane, dane + n); int w = 1; for(int i = 1; i < n; ++i) { if(dane[i - 1] == dane[i]) w++; else{ wyst.push_back(w); w = 1; } } wyst.push_back(w); sort(wyst.begin(), wyst.end(), greater<int>()); //for(int i : wyst) cout << i << ' '; int k = wyst.size() - 1; int res = 0; int ile = 0; for(int i = 0; i < wyst.size(); ++i) { ile = 0; if(wyst[i] > 0) { res++; while(ile < wyst[i] - 1 && k > i) { if(ile + wyst[k] > wyst[i] - 1) { int add = wyst[i] - 1 - ile; wyst[k] -= add; ile += add; } else { ile += wyst[k]; wyst[k] = 0; k--; } } } } cout << res; } |