#include <bits/stdc++.h> using namespace std; int main() { // ifstream cin("tests/0a.in"); cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); int n, tmp; cin >> n; map<int, int> counterMap; for (int i = 0; i < n; i++) { cin >> tmp; counterMap[tmp]++; } vector<int> counter; for (map<int, int>::iterator it = counterMap.begin(); it != counterMap.end(); ++it) { counter.push_back(it->second); } sort(counter.begin(), counter.end()); int minimalSequencesCount = 0; int frontIndex = 0; int liderIndex = counter.size(); while (liderIndex > frontIndex) { liderIndex--; minimalSequencesCount++; tmp = counter[liderIndex] - 1; for (; frontIndex < liderIndex; frontIndex++) { if (counter[frontIndex] <= tmp) { tmp -= counter[frontIndex]; } else { counter[frontIndex] -= tmp; break; } } } cout << minimalSequencesCount << endl; // prints 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 | #include <bits/stdc++.h> using namespace std; int main() { // ifstream cin("tests/0a.in"); cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); int n, tmp; cin >> n; map<int, int> counterMap; for (int i = 0; i < n; i++) { cin >> tmp; counterMap[tmp]++; } vector<int> counter; for (map<int, int>::iterator it = counterMap.begin(); it != counterMap.end(); ++it) { counter.push_back(it->second); } sort(counter.begin(), counter.end()); int minimalSequencesCount = 0; int frontIndex = 0; int liderIndex = counter.size(); while (liderIndex > frontIndex) { liderIndex--; minimalSequencesCount++; tmp = counter[liderIndex] - 1; for (; frontIndex < liderIndex; frontIndex++) { if (counter[frontIndex] <= tmp) { tmp -= counter[frontIndex]; } else { counter[frontIndex] -= tmp; break; } } } cout << minimalSequencesCount << endl; // prints return 0; } |