#include <bits/stdc++.h>
int n;
int T[300'005];
int output[300'005];
std::priority_queue<std::tuple<int, int, int>> pq;
std::unordered_map<int, int> m;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> n;
for (int i = 0; i < n; ++i) {
std::cin >> T[i];
m[T[i]]++;
}
for (auto& [k, v] : m) {
pq.push({v, v, 1});
}
int i = n;
while (!pq.empty() && i > 0) {
auto [next_change, init_val, occ] = pq.top();
pq.pop();
while (i != next_change) {
output[i - 1] = output[i];
--i;
}
if (i == 0) {
break;
}
int new_next_change = init_val / (occ + 1);
++output[i];
pq.push({new_next_change, init_val, occ + 1});
}
for (int i = 1; i <= n; ++i) {
std::cout << output[i] * i << " ";
}
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 | #include <bits/stdc++.h> int n; int T[300'005]; int output[300'005]; std::priority_queue<std::tuple<int, int, int>> pq; std::unordered_map<int, int> m; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); std::cin >> n; for (int i = 0; i < n; ++i) { std::cin >> T[i]; m[T[i]]++; } for (auto& [k, v] : m) { pq.push({v, v, 1}); } int i = n; while (!pq.empty() && i > 0) { auto [next_change, init_val, occ] = pq.top(); pq.pop(); while (i != next_change) { output[i - 1] = output[i]; --i; } if (i == 0) { break; } int new_next_change = init_val / (occ + 1); ++output[i]; pq.push({new_next_change, init_val, occ + 1}); } for (int i = 1; i <= n; ++i) { std::cout << output[i] * i << " "; } return 0; } |
English