#include <cstdio> #include <algorithm> const int max_n = 500100; int n; std::pair<int, int> a[max_n]; int can[max_n]; char out[max_n]; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i].first); a[i].second = i; can[i] = 0; out[i] = 'N'; } std::sort(a, a + n); long long pref = 0; for (int i = 0; i < n;) { int j = i + 1; while (j < n && a[i].first == a[j].first) ++j; if (pref == 0 && j - i > 1) { for (int k = i; k < j; ++k) can[k] = 0, pref += a[k].first; i = j; continue; } for (int k = i; k < j; ++k) pref += a[k].first; for (int k = i; k < j; ++k) can[k] = (j == n || pref > a[j].first); i = j; } for (int i = n - 1; i >= 0; --i) { if (can[i] == 0) break; out[a[i].second] = 'T'; } out[n] = 0; printf("%s\n", out); 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 | #include <cstdio> #include <algorithm> const int max_n = 500100; int n; std::pair<int, int> a[max_n]; int can[max_n]; char out[max_n]; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i].first); a[i].second = i; can[i] = 0; out[i] = 'N'; } std::sort(a, a + n); long long pref = 0; for (int i = 0; i < n;) { int j = i + 1; while (j < n && a[i].first == a[j].first) ++j; if (pref == 0 && j - i > 1) { for (int k = i; k < j; ++k) can[k] = 0, pref += a[k].first; i = j; continue; } for (int k = i; k < j; ++k) pref += a[k].first; for (int k = i; k < j; ++k) can[k] = (j == n || pref > a[j].first); i = j; } for (int i = n - 1; i >= 0; --i) { if (can[i] == 0) break; out[a[i].second] = 'T'; } out[n] = 0; printf("%s\n", out); return 0; } |