#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; } |
English