#include <bits/stdc++.h> using namespace std; bool pos(const int& idx, const vector<int>& w, const vector<int>& srt) { long long s = w[idx]; for (auto& j : srt) { if (idx == j) continue; if (s <= w[j]) return false; s += w[j]; } return true; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> w(n), srt(n); iota(srt.begin(), srt.end(), 0); for (auto& x : w) cin >> x; sort(srt.begin(), srt.end(), [&w](const int& i, const int& j){ return w[i] < w[j]; }); int l = -1, r = n; while (l+1 < r) { int m = (l + r)/2; if (pos(srt[m], w, srt)) r = m; else l = m; } int min_w = r == n ? INT32_MAX : w[srt[r]]; for (auto& x : w) cout << (x < min_w ? 'N' : 'T'); }
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 | #include <bits/stdc++.h> using namespace std; bool pos(const int& idx, const vector<int>& w, const vector<int>& srt) { long long s = w[idx]; for (auto& j : srt) { if (idx == j) continue; if (s <= w[j]) return false; s += w[j]; } return true; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> w(n), srt(n); iota(srt.begin(), srt.end(), 0); for (auto& x : w) cin >> x; sort(srt.begin(), srt.end(), [&w](const int& i, const int& j){ return w[i] < w[j]; }); int l = -1, r = n; while (l+1 < r) { int m = (l + r)/2; if (pos(srt[m], w, srt)) r = m; else l = m; } int min_w = r == n ? INT32_MAX : w[srt[r]]; for (auto& x : w) cout << (x < min_w ? 'N' : 'T'); } |