华为 · 贪心 · 算法编程题
华为 贪心 T ≤ 10 时限 1 秒 / 32 MB

题目描述

对于给定由小写字母构成的字符串，定义字符串的“漂亮度”为该字符串中所有字母“漂亮度”的总和。
每一个字母的“漂亮度”将由你来确定，具体规则如下：
每一个字母的“漂亮度”为 1 到 26 之间的整数；
没有两个字母的“漂亮度”相同。
现在，你需要确定每个字母的“漂亮度”，以使得字符串的“漂亮度”最大。

输入输出

输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤ T≤ 10) 代表数据组数，每组测试数据描述如下：
在一行上输入一个长度为 1 ≤ len(s) ≤ 10^4 、仅由小写字母构成的字符串 s 。
输出描述
对于每一组测试数据，输出一个整数，表示字符串的最大“漂亮度”。

样例共 1 组

样例 1 · 对于第一组测试数据，其中一种最优的分配方案是： 将字符 `a' 的漂亮度分配为 26 ； 将字符 `n' 的漂亮度分配为 25 ； 将字符 `g', `z', `h', `s' 的漂亮度依次分配为 24 21 ； 其余字符随意分配； 最终，得到字符串的“漂亮度”为 (26 + 25) × 2 + (24 + 23 + 22 + 21) = 192 。 对于第二组测试数据，其中一种最优的分配方案是： 将字符 `i' 的漂亮度分配为 26 ； 将字符 `l' 的漂亮度分配为 25 ； 将字符 `s' 的漂亮度分配为 24 ； 其余字符随意分配； 最终，得到字符串的“漂亮度”为 26 × 2 + (25 + 24) = 101 。
输入
2
zhangsan
lisi
输出
192
101

算法解析依据充分

考点：字符串 · 贪心

数据规模 T ≤ 10 ｜ 限制 1 秒 / 32MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 10
  • 元素值域：s ≤ 1e4（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 数据规模 T ≤ 10，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 / zhangsan / lisi → 输出 192 / 101

对于第一组测试数据，其中一种最优的分配方案是：

将字符 `a' 的漂亮度分配为 26 ；

将字符 `n' 的漂亮度分配为 25 ；

将字符 g', z', h', s' 的漂亮度依次分配为 24 21 ；

其余字符随意分配；

最终，得到字符串的“漂亮度”为 (26 + 25) × 2 + (24 + 23 + 22 + 21) = 192 。

对于第二组测试数据，其中一种最优的分配方案是：

将字符 `i' 的漂亮度分配为 26 ；

将字符 `l' 的漂亮度分配为 25 ；

将字符 `s' 的漂亮度分配为 24 ；

其余字符随意分配；

最终，得到字符串的“漂亮度”为 26 × 2 + (25 + 24) = 101 。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：华为机试编程模拟题10。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解