#include <bits/stdc++.h> using namespace std; bool symuluj(vector <long long> & t2, int r){ long long ryba = 0; for (int i=r;i>=0;i--){ if (t2[0] < t2[r] || r==0){ ryba += t2[i]; } } for (int i=r+1;i<t2.size();i++){ if (ryba<=t2[i]){ return 0; } ryba+=t2[i]; } return 1; } int main(){ int n; cin >> n; vector <long long> t2; vector <long long> t3; for (int i=0; i<n;i++){ long long a; cin >> a; t2.push_back(a); t3.push_back(a); } sort(t2.begin(),t2.end()); int wynik=0; /*for (int i=0;i<n;i++){ cout << t2[i]<<" "<<symuluj(t2,i)<<endl; }*/ int a=0, b=n; while(a<b){ int s = (a+b)/2; if (!symuluj(t2,s)){ a=s+1; }else{ b=s; } } for (int i=0; i<n;i++){ if (t3[i]>t2[a-1]){ cout << "T"; }else{ cout << "N"; } } cout << endl; }
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 | #include <bits/stdc++.h> using namespace std; bool symuluj(vector <long long> & t2, int r){ long long ryba = 0; for (int i=r;i>=0;i--){ if (t2[0] < t2[r] || r==0){ ryba += t2[i]; } } for (int i=r+1;i<t2.size();i++){ if (ryba<=t2[i]){ return 0; } ryba+=t2[i]; } return 1; } int main(){ int n; cin >> n; vector <long long> t2; vector <long long> t3; for (int i=0; i<n;i++){ long long a; cin >> a; t2.push_back(a); t3.push_back(a); } sort(t2.begin(),t2.end()); int wynik=0; /*for (int i=0;i<n;i++){ cout << t2[i]<<" "<<symuluj(t2,i)<<endl; }*/ int a=0, b=n; while(a<b){ int s = (a+b)/2; if (!symuluj(t2,s)){ a=s+1; }else{ b=s; } } for (int i=0; i<n;i++){ if (t3[i]>t2[a-1]){ cout << "T"; }else{ cout << "N"; } } cout << endl; } |