#include <algorithm> #include <iostream> #include <vector> using namespace std; bool Check(int ind, vector<pair<int, int>>&v) { long long M = v[ind].first; for(int i = 0; i < (int)v.size(); i++) { if(i == ind) continue; if(v[i].first >= M) return false; M += v[i].first; } return true; } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; vector<pair<int, int>>v(n); vector<bool>result(n, false); for(int i = 0; i < n; i++) { cin >> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); int beg = 0, end = n - 1; while(beg <= end) { int mid = (beg + end) / 2; if(Check(mid, v)) { end = mid - 1; } else { beg = mid + 1; } } for(int i = beg; i < n; i++) result[v[i].second] = true; for(int i = 0; i < n; i++) cout << (result[i] ? 'T' : 'N'); cout << '\n'; 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 48 49 | #include <algorithm> #include <iostream> #include <vector> using namespace std; bool Check(int ind, vector<pair<int, int>>&v) { long long M = v[ind].first; for(int i = 0; i < (int)v.size(); i++) { if(i == ind) continue; if(v[i].first >= M) return false; M += v[i].first; } return true; } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; vector<pair<int, int>>v(n); vector<bool>result(n, false); for(int i = 0; i < n; i++) { cin >> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); int beg = 0, end = n - 1; while(beg <= end) { int mid = (beg + end) / 2; if(Check(mid, v)) { end = mid - 1; } else { beg = mid + 1; } } for(int i = beg; i < n; i++) result[v[i].second] = true; for(int i = 0; i < n; i++) cout << (result[i] ? 'T' : 'N'); cout << '\n'; return 0; } |