本题有贪心的思想。对于出现次数最多的字符,使用当前可能最大的漂亮度,这样最后的漂亮度可能最大。因此需要统计字符串中每个字符出现的次数,对于出现次数最多的字符令其漂亮度为26,出现次数次多的字符令其漂亮度为25,...,以此类推。
这里统计字符次数用到了unordered_map<char,int>,然后再利用sort()的cmp根据键值对中的值对其进行排序。
#include <iostream> #include <string> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; static bool cmp(const pair<char, int> &p1, const pair<char,int> &p2) { return p1.second > p2.second; } int main(){ int N = 0; cin >> N; cin.get(); unordered_map<char,int> u_map; vector<int> res; int sum = 0; int val = 26; for (int i = 0; i < N; i++) { string s; getline(cin, s, '\n'); // 统计字符串中的字符个数 for (int j = 0; j < s.size(); j++) { if (u_map.find(s[j]) != u_map.end()) { u_map[s[j]]++; } else { u_map[s[j]] = 1; } } // 对unordered_map<char,int>根据值进行排序 vector<pair<char, int>> vec; for (unordered_map<char,int>::iterator iter = u_map.begin(); iter != u_map.end(); iter++) { vec.push_back(make_pair(iter->first, iter->second)); } sort(vec.begin(), vec.end(), cmp); for (vector<pair<char,int>>::iterator iter = vec.begin(); iter != vec.end(); iter++) { sum += val * iter->second; val--; } res.push_back(sum); sum = 0; val = 26; vec.clear(); u_map.clear(); } // 输出 for (vector<int>::iterator iter = res.begin(); iter != res.end(); iter++) { cout << *iter << endl; } }