#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, weight; cin>>n; vector<bool> kings(n, false); vector< pair<long long int, int> > weights(n); vector< long long int > cumsums(n); for (int i = 0; i < n; i++) { cin>>weight; weights.at(i) = make_pair(weight, i); } sort (weights.begin(),weights.end()); long long int cumsum = cumsums.at(0) = weights[0].first; for (int i = 1 ; i < n ; i++) { cumsum += weights[i].first; if (weights[i-1].first < weights[i].first || cumsums[i -1] > weights[i -1].first) { cumsums[i] = cumsum; } else { cumsums[i] = weights[i].first; } } for (int i = n-1; i >=0; i--) { bool isGreater = weights[i].first < cumsums[i]; if (!isGreater) break; if (i == n-1 || weights[i+1].first < cumsums[i]) { kings[weights[i].second] = true; } else { break; } long long int currentWeight = weights[i].first; int k = 0; while (i-k - 1 >= 0 && currentWeight == weights[i - k - 1].first) { kings[weights[i - k - 1].second] = true; k++; } i -= k; } for (int i = 0 ; i < n ; i++){ if (kings[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 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, weight; cin>>n; vector<bool> kings(n, false); vector< pair<long long int, int> > weights(n); vector< long long int > cumsums(n); for (int i = 0; i < n; i++) { cin>>weight; weights.at(i) = make_pair(weight, i); } sort (weights.begin(),weights.end()); long long int cumsum = cumsums.at(0) = weights[0].first; for (int i = 1 ; i < n ; i++) { cumsum += weights[i].first; if (weights[i-1].first < weights[i].first || cumsums[i -1] > weights[i -1].first) { cumsums[i] = cumsum; } else { cumsums[i] = weights[i].first; } } for (int i = n-1; i >=0; i--) { bool isGreater = weights[i].first < cumsums[i]; if (!isGreater) break; if (i == n-1 || weights[i+1].first < cumsums[i]) { kings[weights[i].second] = true; } else { break; } long long int currentWeight = weights[i].first; int k = 0; while (i-k - 1 >= 0 && currentWeight == weights[i - k - 1].first) { kings[weights[i - k - 1].second] = true; k++; } i -= k; } for (int i = 0 ; i < n ; i++){ if (kings[i]) { cout << "T"; } else { cout << "N"; } } cout<<endl; return 0; } |