ACM. HJ45 名字的漂亮度 ●●

HJ45 名字的漂亮度 ●●

描述

给出一个字符串，该字符串仅由小写字母组成，定义这个字符串的“漂亮度”是其所有字母“漂亮度”的总和。
每个字母都有一个“漂亮度”，范围在1到26之间。没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。

给出多个字符串，计算每个字符串最大可能的“漂亮度”。

本题含有多组数据。

数据范围：输入的名字长度满足 $1\le n\le 10000$

输入描述：

第一行一个整数N，接下来N行每行一个字符串

输出描述：

每个字符串可能的最大漂亮程度

示例

输入：
2
zhangsan
lisi
输出：
192
101
说明：
对于样例lisi，让i的漂亮度为26，l的漂亮度为25，s的漂亮度为24，lisi的漂亮度为25+26+24+26=101.

题解

1. 数组统计 + 贪心

遍历字符串，统计字母出现的频次，统计完成后，因为最终结果只需要求分数，因此不需要知道某个字母对应的频次，所以将数组从大到小排序，频次越大，漂亮度越高（最高为26），最后计算总漂亮度。

• 时间复杂度：$O(Nlen)$，需要遍历每个字符串的每个字母。
• 空间复杂度：$O(len+26)$，存储字符串所需空间。

/* 
    HJ45 名字的漂亮度
*/

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    while(n--){
        string str;
        cin >> str;
        vector<int> table(26, 0);
        int cnt = 0;
        for(char ch: str){    
            if(table[ch-'a'] == 0) ++cnt;        // 统计频次，以及字母数量
            ++table[ch-'a'];
        }                                        // 按频次从大到小排序
        sort(table.begin(), table.end(), [=](int a, int b){    // greater<int>()
            return a > b;
        });
        int ans = 0, score = 26;                // 计算分数，频次越大，分数越高
        for(int i = 0; i < cnt; ++i){
            ans += table[i] * score;
            --score;
        }
        cout << ans << 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