#include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 1000006; int n; int t2[MAXN]; int t[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &t[i]); t2[i] = t[i]; } sort(t + 1, t + 1 + n); int best = n + 1; int l = 1, p = n + 1; while (l != p) { int sr = (l + p) / 2; bool czy = false; LL act = t[sr]; for (int i = 1; i <= n; ++i) { if (i == sr) { continue; } if (act > t[i]) { act += (LL)t[i]; } } if (act > t[n]) { czy = true; } if (czy) { best = min(best, sr); p = sr; } else { l = sr + 1; } } t[n + 1] = 1000000007; for (int i = 1; i <= n; ++i) { if (t2[i] >= t[best]) { printf("T"); } else { printf("N"); } } printf("\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 | #include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 1000006; int n; int t2[MAXN]; int t[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &t[i]); t2[i] = t[i]; } sort(t + 1, t + 1 + n); int best = n + 1; int l = 1, p = n + 1; while (l != p) { int sr = (l + p) / 2; bool czy = false; LL act = t[sr]; for (int i = 1; i <= n; ++i) { if (i == sr) { continue; } if (act > t[i]) { act += (LL)t[i]; } } if (act > t[n]) { czy = true; } if (czy) { best = min(best, sr); p = sr; } else { l = sr + 1; } } t[n + 1] = 1000000007; for (int i = 1; i <= n; ++i) { if (t2[i] >= t[best]) { printf("T"); } else { printf("N"); } } printf("\n"); } |