#include <iostream> #include <algorithm> #include <vector> using namespace std; struct sum { long long mass; long long ID; bool canbeKing = 1; }; bool sMass(sum a, sum b) { return a.mass < b.mass; } bool sID(sum a, sum b) { return a.ID < b.ID; } vector<sum> sumy; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n; cin >> n; sum t; for (long long i = 0; i < n; i++) { cin >> t.mass; t.ID = i; sumy.push_back(t); } if (n == 1) { cout << "T"; return 0; } sort(sumy.begin(), sumy.end(), sMass); long long lightest = sumy[0].mass; for (long long i = 1; i < sumy.size() && sumy[i].mass == lightest; i++) { sumy[i].canbeKing = false; } long long count = 0; long long treshold = 0; for (long long i = 0; i < n - 1; i++) { count += sumy[i].mass; if (sumy[i + 1].mass >= count) { treshold = i + 1; } } for (long long i = 0; i < treshold; i++) { sumy[i].canbeKing = false; } sort(sumy.begin(), sumy.end(), sID); for (long long i = 0; i < n; i++) { if (sumy[i].canbeKing) { cout << "T"; } else { 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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <iostream> #include <algorithm> #include <vector> using namespace std; struct sum { long long mass; long long ID; bool canbeKing = 1; }; bool sMass(sum a, sum b) { return a.mass < b.mass; } bool sID(sum a, sum b) { return a.ID < b.ID; } vector<sum> sumy; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n; cin >> n; sum t; for (long long i = 0; i < n; i++) { cin >> t.mass; t.ID = i; sumy.push_back(t); } if (n == 1) { cout << "T"; return 0; } sort(sumy.begin(), sumy.end(), sMass); long long lightest = sumy[0].mass; for (long long i = 1; i < sumy.size() && sumy[i].mass == lightest; i++) { sumy[i].canbeKing = false; } long long count = 0; long long treshold = 0; for (long long i = 0; i < n - 1; i++) { count += sumy[i].mass; if (sumy[i + 1].mass >= count) { treshold = i + 1; } } for (long long i = 0; i < treshold; i++) { sumy[i].canbeKing = false; } sort(sumy.begin(), sumy.end(), sID); for (long long i = 0; i < n; i++) { if (sumy[i].canbeKing) { cout << "T"; } else { cout << "N"; } } } |