#include<bits/stdc++.h> using namespace std; long long n,a[500001],b[500001],p=0,k,s,masa; bool czy; int main() { scanf("%lld",&n); for(long long i=0;i<n;++i) { scanf("%lld",&a[i]); b[i]=a[i]; } a[n]=LONG_LONG_MAX; b[n]=LONG_LONG_MAX; sort(a,a+n); k=n; s=k/2; while(s!=p) { masa=a[s]; czy=1; for(long long i=0;i<s;++i) { if(masa<=a[i]) { czy=0; break; } masa+=a[i]; } if(czy) { for(long long i=s+1;i<n;++i) { if(masa<=a[i]) { czy=0; break; } masa+=a[i]; } } if(czy) { k=s; } else p=s; s=(p+k)/2; } ++s; for(long long i=0;i<n;++i) { if(b[i]>=a[s]) putchar('T'); else putchar('N'); } 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<bits/stdc++.h> using namespace std; long long n,a[500001],b[500001],p=0,k,s,masa; bool czy; int main() { scanf("%lld",&n); for(long long i=0;i<n;++i) { scanf("%lld",&a[i]); b[i]=a[i]; } a[n]=LONG_LONG_MAX; b[n]=LONG_LONG_MAX; sort(a,a+n); k=n; s=k/2; while(s!=p) { masa=a[s]; czy=1; for(long long i=0;i<s;++i) { if(masa<=a[i]) { czy=0; break; } masa+=a[i]; } if(czy) { for(long long i=s+1;i<n;++i) { if(masa<=a[i]) { czy=0; break; } masa+=a[i]; } } if(czy) { k=s; } else p=s; s=(p+k)/2; } ++s; for(long long i=0;i<n;++i) { if(b[i]>=a[s]) putchar('T'); else putchar('N'); } return 0; } |