本题有贪心的思想。对于出现次数最多的字符,使用当前可能最大的漂亮度,这样最后的漂亮度可能最大。因此需要统计字符串中每个字符出现的次数,对于出现次数最多的字符令其漂亮度为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;
}
}

京公网安备 11010502036488号