#include <bits/stdc++.h> constexpr int MAXN = 5e5 + 10; using namespace std; int n; int a[MAXN], in[MAXN]; long long pref[MAXN]; bool cmp(int c, int b) { return a[c] < a[b]; } int mini = 1e9 + 10; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; in[i] = i; mini = min(mini, a[i]); } sort(in + 1, in + n + 1, cmp); for (int i = 1; i <= n; i++) pref[i] = a[in[i]] + pref[i-1]; //for (int i = 1; i <=n; i++) //cout << pref[i] << ' '; vector<char>res(n, 'N'); for (int i = n; i > 1; i--) { if (a[in[i]] == mini || pref[i] <= a[in[i+1]]) break; res[in[i]-1] = 'T'; } for (auto i : res) cout << i; }
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 | #include <bits/stdc++.h> constexpr int MAXN = 5e5 + 10; using namespace std; int n; int a[MAXN], in[MAXN]; long long pref[MAXN]; bool cmp(int c, int b) { return a[c] < a[b]; } int mini = 1e9 + 10; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; in[i] = i; mini = min(mini, a[i]); } sort(in + 1, in + n + 1, cmp); for (int i = 1; i <= n; i++) pref[i] = a[in[i]] + pref[i-1]; //for (int i = 1; i <=n; i++) //cout << pref[i] << ' '; vector<char>res(n, 'N'); for (int i = n; i > 1; i--) { if (a[in[i]] == mini || pref[i] <= a[in[i+1]]) break; res[in[i]-1] = 'T'; } for (auto i : res) cout << i; } |