#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'); } } |