跳到主要内容

小美的 MT

题目描述​

MT 是美团的缩写，因此小美很喜欢这两个字母。

现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次,每次可以修改任意一个字符。

小美想知道，操作结束后最多共有多少个M和T字符？

输入描述​

第一行输入两个正整数n,k，代表字符串长度和操作次数。

第二行输入一个长度为n的、仅由大写字母组成的字符串。

输出描述​

输出操作结束后最多共有多少个M和T字符。

示例​

输入：
5 2
MTUAN

输出：
4

解释：
修改第三个和第五个字符，形成的字符串为 `MTTAM`，这样共有 4 个`M`和`T`。

解题思路​

这是一个贪心算法问题。我们的目标是最大化字符串中'M'和'T'字符的数量。

贪心算法

  1. 统计原字符串中已有的'M'和'T'字符数量
  2. 计算还能修改多少个其他字符为'M'或'T'
  3. 结果等于原有数量加上可修改数量

时间复杂度：O(n) 空间复杂度：O(n)

C++ 解法​

#include <string>
#include <iostream>

int main()
{
   int n, k;
   std::cin >> n >> k;

   string str;
   std::cin >> str;

   int mtCount = 0;
   for (const auto &c : str) {
      if (c == 'M' || c == 'T') {
         mtCount++;
      }
   }

   int changeable = min(k, n - mtCount);
   int maxCount = changeable + mtCount;
   std::cout << maxCount;
   return 0;
}