#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000000;
pair<int, int> weight[MAX_N];
map<int, int> cnt;
bool res[MAX_N];
long long sum = 0;
int n;
int main() {
cin.tie(0); ios_base::sync_with_stdio(false);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> weight[i].first;
weight[i].second = i;
cnt[weight[i].first]++;
sum += weight[i].first;
}
sort(weight, weight+n);
if(weight[0].first == weight[n-1].first) {
for(int i = 0; i < n; i++) {
cout << 'N';
}
return 0;
}
int j = n-1;
for(int i = n-1; i >= 0; i--) {
while(weight[j].first >= weight[i].first && j != -1) {
sum -= weight[j].first;
j--;
}
long long mod = 0;
if(sum > 0) {
mod = cnt[weight[i].first] * weight[i].first;
}
if(sum + mod > weight[i+1].first) {
res[weight[i].second] = true;
}
else {
break;
}
}
for(int i = 0; i < n; i++) {
cout << (res[i] ? 'T' : '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 57 | #include <bits/stdc++.h> using namespace std; const int MAX_N = 1000000; pair<int, int> weight[MAX_N]; map<int, int> cnt; bool res[MAX_N]; long long sum = 0; int n; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> n; for(int i = 0; i < n; i++) { cin >> weight[i].first; weight[i].second = i; cnt[weight[i].first]++; sum += weight[i].first; } sort(weight, weight+n); if(weight[0].first == weight[n-1].first) { for(int i = 0; i < n; i++) { cout << 'N'; } return 0; } int j = n-1; for(int i = n-1; i >= 0; i--) { while(weight[j].first >= weight[i].first && j != -1) { sum -= weight[j].first; j--; } long long mod = 0; if(sum > 0) { mod = cnt[weight[i].first] * weight[i].first; } if(sum + mod > weight[i+1].first) { res[weight[i].second] = true; } else { break; } } for(int i = 0; i < n; i++) { cout << (res[i] ? 'T' : 'N'); } } |
English