#include <iostream> #include <algorithm> using namespace std; const int max_array = 500001; int counts[max_array] = { 0 }; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int number; cin >> number; counts[number]++; } sort(counts, counts + n + 1); int sequence = 0; int remaining_elements = n; for (int i = n; i >= 0 && remaining_elements > 0; --i) { if (counts[i] == 0) continue; int max_count = counts[i]; sequence++; remaining_elements -= max_count; if (remaining_elements > 0) { remaining_elements -= min(remaining_elements, max_count - 1); } } cout << sequence << endl; 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 | #include <iostream> #include <algorithm> using namespace std; const int max_array = 500001; int counts[max_array] = { 0 }; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int number; cin >> number; counts[number]++; } sort(counts, counts + n + 1); int sequence = 0; int remaining_elements = n; for (int i = n; i >= 0 && remaining_elements > 0; --i) { if (counts[i] == 0) continue; int max_count = counts[i]; sequence++; remaining_elements -= max_count; if (remaining_elements > 0) { remaining_elements -= min(remaining_elements, max_count - 1); } } cout << sequence << endl; return 0; } |