#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"; } |
English