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