#include <iostream> #include <vector> #include <string> #include <map> #include <algorithm> using namespace std; map<int, bool> king; int main() { int count, maxVal, minVal; ios::sync_with_stdio(false); cin >> count; vector<int> weight(count); vector<int> data(count); vector<int> prSum(count); vector<int> maxWeight(count); string answer(count, 'N'); cin >> weight[0]; data[0] = minVal = maxVal = weight[0]; for(int i=1; i<count; ++i) { cin >> weight[i]; data[i] = weight[i]; king[weight[i]] = false; if(weight[i] > maxVal) maxVal = weight[i]; if(weight[i] < minVal) minVal = weight[i]; } if(count == 1) { cout << "T" << endl; return 0; } sort(weight.begin(), weight.end()); prSum[0] = weight[0]; for(int i=1; i<count; ++i) { prSum[i] = prSum[i-1] + weight[i]; if(weight[i] > minVal) maxWeight[i] = prSum[i]; else maxWeight[i] = weight[i]; } for(int i=1; i<count; ++i) { if(maxWeight[i] > maxVal) { king[weight[i]] = true; continue; } for(int j=i+1; j<count; ++j) { if(maxWeight[i] > weight[j]) { maxWeight[i] += weight[j]; if(maxWeight[i] > maxVal) { king[weight[i]] = true; } } else { break; } } } for(int i=0; i<count; ++i) { if(king[data[i]]) { answer[i] = 'T'; } } cout << answer << 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <iostream> #include <vector> #include <string> #include <map> #include <algorithm> using namespace std; map<int, bool> king; int main() { int count, maxVal, minVal; ios::sync_with_stdio(false); cin >> count; vector<int> weight(count); vector<int> data(count); vector<int> prSum(count); vector<int> maxWeight(count); string answer(count, 'N'); cin >> weight[0]; data[0] = minVal = maxVal = weight[0]; for(int i=1; i<count; ++i) { cin >> weight[i]; data[i] = weight[i]; king[weight[i]] = false; if(weight[i] > maxVal) maxVal = weight[i]; if(weight[i] < minVal) minVal = weight[i]; } if(count == 1) { cout << "T" << endl; return 0; } sort(weight.begin(), weight.end()); prSum[0] = weight[0]; for(int i=1; i<count; ++i) { prSum[i] = prSum[i-1] + weight[i]; if(weight[i] > minVal) maxWeight[i] = prSum[i]; else maxWeight[i] = weight[i]; } for(int i=1; i<count; ++i) { if(maxWeight[i] > maxVal) { king[weight[i]] = true; continue; } for(int j=i+1; j<count; ++j) { if(maxWeight[i] > weight[j]) { maxWeight[i] += weight[j]; if(maxWeight[i] > maxVal) { king[weight[i]] = true; } } else { break; } } } for(int i=0; i<count; ++i) { if(king[data[i]]) { answer[i] = 'T'; } } cout << answer << endl; return 0; } |