#include<iostream> #include<vector> #include<algorithm> #include<map> using namespace std; int main() { ios_base::sync_with_stdio(0); int n; cin>>n; vector<int> T(n),O; map<int,bool> M; vector<long long> S(n); for(auto &i : T) {cin>>i; M[i]=false;} O=T; sort(T.begin(),T.end()); vector<long long> P(n); P[0]=T[0]; for(int i=1 ; i<n ; i++) { P[i]=P[i-1]+T[i]; if(T[i]!=T[i-1]) S[i]=P[i-1]; else S[i]=S[i-1]; } int wsk=n-1; int ostatni=T[n-1]; while(wsk) { //cout<<T[wsk]<<" "<<S[wsk]<<endl; //cout<<"ostatni "<<ostatni<<endl; if(S[wsk]>0) S[wsk]=P[wsk]-T[wsk]; //cout<<"Pwsk "<<P[wsk]<<endl; if(T[wsk]+S[wsk]>ostatni) { ostatni=T[wsk]; M[T[wsk]] = true; } wsk--; } for(int i=0 ; i<n ; i++) { if(M[O[i]]) cout<<"T"; else cout<<"N"; } cout<<endl; 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 41 42 43 44 | #include<iostream> #include<vector> #include<algorithm> #include<map> using namespace std; int main() { ios_base::sync_with_stdio(0); int n; cin>>n; vector<int> T(n),O; map<int,bool> M; vector<long long> S(n); for(auto &i : T) {cin>>i; M[i]=false;} O=T; sort(T.begin(),T.end()); vector<long long> P(n); P[0]=T[0]; for(int i=1 ; i<n ; i++) { P[i]=P[i-1]+T[i]; if(T[i]!=T[i-1]) S[i]=P[i-1]; else S[i]=S[i-1]; } int wsk=n-1; int ostatni=T[n-1]; while(wsk) { //cout<<T[wsk]<<" "<<S[wsk]<<endl; //cout<<"ostatni "<<ostatni<<endl; if(S[wsk]>0) S[wsk]=P[wsk]-T[wsk]; //cout<<"Pwsk "<<P[wsk]<<endl; if(T[wsk]+S[wsk]>ostatni) { ostatni=T[wsk]; M[T[wsk]] = true; } wsk--; } for(int i=0 ; i<n ; i++) { if(M[O[i]]) cout<<"T"; else cout<<"N"; } cout<<endl; return 0; } |