#include <iostream> #include <map> int main() { int n; std::cin >> n; std::map<int, int> counts; int sizes[n]; for (int i = 0; i < n; ++i) { std::cin >> sizes[i]; counts.insert({sizes[i], 0}); counts[sizes[i]] += 1; } if (counts.size() == 1) { if (n == 1) { std::cout << "T\n"; } else { for (int i = 0; i < n; ++i) { std::cout << "N"; } std::cout << "\n"; } return 0; } int top = counts.rbegin()->first; auto it = counts.begin(); int min = it->first + 1; long long food = it->first * it->second; ++it; for (;;) { food += it->first * it->second; if (food > top) { break; } ++it; if (it == counts.end()) { break; } if (food <= it->first) { min = it->first; } } for (int i = 0; i < n; ++i) { std::cout << (sizes[i] >= min ? "T" : "N"); } std::cout << "\n"; }
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 49 50 51 52 | #include <iostream> #include <map> int main() { int n; std::cin >> n; std::map<int, int> counts; int sizes[n]; for (int i = 0; i < n; ++i) { std::cin >> sizes[i]; counts.insert({sizes[i], 0}); counts[sizes[i]] += 1; } if (counts.size() == 1) { if (n == 1) { std::cout << "T\n"; } else { for (int i = 0; i < n; ++i) { std::cout << "N"; } std::cout << "\n"; } return 0; } int top = counts.rbegin()->first; auto it = counts.begin(); int min = it->first + 1; long long food = it->first * it->second; ++it; for (;;) { food += it->first * it->second; if (food > top) { break; } ++it; if (it == counts.end()) { break; } if (food <= it->first) { min = it->first; } } for (int i = 0; i < n; ++i) { std::cout << (sizes[i] >= min ? "T" : "N"); } std::cout << "\n"; } |