#include<bits/stdc++.h> using namespace std; pair <int,int> tab[500005]; long long sp[500005]; bool w[500005]; int main() { int n; cin >> n; for(int i=0 ; i<n; i++) { int a; cin >> a; tab[i]=make_pair(a,i); } sort(tab,tab+n); sp[0]=tab[0].first; for(int i=0; i<n; i++) { if(i!=0) { sp[i]=sp[i-1]; if(tab[i].first!=tab[i-1].first) { sp[i]+=tab[i].first; } } } for(int i=0; i<n; i++) { int a=i; int x=0; while(sp[a]>tab[a+1].first && a<n) { x++; a++; } if(x==n-i) { w[tab[i].second]=1; } } for(int i=0; i<n; i++) { if(w[i]==1) { 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 48 49 50 51 52 53 54 55 56 | #include<bits/stdc++.h> using namespace std; pair <int,int> tab[500005]; long long sp[500005]; bool w[500005]; int main() { int n; cin >> n; for(int i=0 ; i<n; i++) { int a; cin >> a; tab[i]=make_pair(a,i); } sort(tab,tab+n); sp[0]=tab[0].first; for(int i=0; i<n; i++) { if(i!=0) { sp[i]=sp[i-1]; if(tab[i].first!=tab[i-1].first) { sp[i]+=tab[i].first; } } } for(int i=0; i<n; i++) { int a=i; int x=0; while(sp[a]>tab[a+1].first && a<n) { x++; a++; } if(x==n-i) { w[tab[i].second]=1; } } for(int i=0; i<n; i++) { if(w[i]==1) { cout << "T"; } else { cout << "N"; } } } |