1000ms

Difficulty: 3

所属公司 : 饿了么

时间 :2025年4月12日(算法方向)

算法与标签>贪心算法

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

目标是把铭牌变成字典序最小的字符串。ASCII 中大写字母一律小于小写字母，因此每个位置的最优结果是字符 $A$ 。

从左到右贪心处理，优先把更靠前的位置变得更小：

若当前是大写字母：已经是 $A$ 则无需操作；否则用 $1$ 次「大写改任意大写」即可变成 $A$ 。
若当前是小写 $a$ ：用 $1$ 次大小写转换即可变成 $A$ 。
若当前是其它小写字母：有 $2$ 次额度时，先转成对应大写再改成 $A$ ；只剩 $1$ 次时，至少转成对应大写（仍优于原小写）；没有额度则保持不变。

题目内容

工坊里有一块长度为 $n$ 的铭牌，上面刻着仅由大小写英文字母组成的字符串 $s$ 。工匠最多可以施展 $k$ 次重铸，每次选择下列操作之一：

将某个大写字母改成与它对应的小写字母（例如将 $A$ 改成 $a$ ）；
将某个小写字母改成与它对应的大写字母（例如将 $k$ 改成 $K$ ）；
将某个大写字母改成任意一个大写字母；
将某个小写字母改成任意一个小写字母。

请给出重铸后字典序最小的铭牌内容。

字典序从左到右逐位比较 ASCII 码：满足 $A < B < \cdots < Z < a < \cdots < z$ ，编码更小的更靠前；若其中一个是另一个的前缀，则较短者更小。