#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int32_t main(){ ios::sync_with_stdio(false); int n; cin >> n; vector<int> tab(n); vector<pii> sorted(n); for(int i=0;i<n;i++) { cin >> tab[i]; sorted[i] = {tab[i],i}; } sort(sorted.begin(), sorted.end()); auto solve = [&](int i) { long long siz = sorted[i].first; for(int j=0;j<n;j++) { if(j == i) continue; if(sorted[j].first >= siz) return 0; siz += sorted[j].first; } return 1; }; int low = 0, high = n-1, mid,lg=-1; while(low <= high) { mid = (low+high)/2; if(solve(mid)) { high = mid-1; lg = mid; } else { low = mid+1; } } if(lg == -1) cout<<string(n,'N'); else for(int i=0;i<n;i++) if(tab[i] >= sorted[lg].first) cout<<"T"; else cout<<"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 | #include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int32_t main(){ ios::sync_with_stdio(false); int n; cin >> n; vector<int> tab(n); vector<pii> sorted(n); for(int i=0;i<n;i++) { cin >> tab[i]; sorted[i] = {tab[i],i}; } sort(sorted.begin(), sorted.end()); auto solve = [&](int i) { long long siz = sorted[i].first; for(int j=0;j<n;j++) { if(j == i) continue; if(sorted[j].first >= siz) return 0; siz += sorted[j].first; } return 1; }; int low = 0, high = n-1, mid,lg=-1; while(low <= high) { mid = (low+high)/2; if(solve(mid)) { high = mid-1; lg = mid; } else { low = mid+1; } } if(lg == -1) cout<<string(n,'N'); else for(int i=0;i<n;i++) if(tab[i] >= sorted[lg].first) cout<<"T"; else cout<<"N"; } |