题解 | #小红的大小写字母#

题目链接

小红的大小写字母

题目描述

小红拿到了一个仅由大小写字母构成的长度为 $n$ 的字符串，她每次操作可以将一个字符在大小写之间切换（例如将 'a' 变为 'A'，或将 'A' 变为 'a'）。

她希望经过恰好 $k$ 次操作后，大写字母的数量尽可能多。请输出最终字符串中大写字母的数量。

输入:

两个整数 $n$ 和 $k$ 。
一个长度为 $n$ 、由大小写字母构成的字符串 $s$ 。

输出:

一个整数，表示经过恰好 $k$ 次操作后，最终字符串中大写字母的最大数量。

解题思路

这是一个需要一些逻辑推理的贪心问题。问题的关键在于，我们不仅要最大化大写字母的数量，还必须确保总操作次数恰好为 $k$ 。

我们可以反向思考：假设我们最终的目标是得到 $T$ 个大写字母，这个目标是否可行？需要满足什么条件？

计算初始状态：首先，我们遍历一次字符串，统计出初始的大写字母数量，记为 $\text{upper_count}$ 。
计算最小操作数: 要想从 $\text{upper_count}$ 个大写字母的状态，转变为 $T$ 个大写字母的状态，最少需要多少次操作？
- 这个最直接的方式就是只翻转那些状态不对的字母。例如，如果 $T > \text{upper_count}$ ，我们就需要把 $T - \text{upper_count}$ 个小写字母变成大写。
- 因此，这个最少的必要操作次数就是 $|T - \text{upper_count}|$ 。我们将其记为 $\text{min_ops}$ 。
处理剩余操作数：我们总共有 $k$ 次操作。在完成了 $\text{min_ops}$ 次必要操作后，还剩下 $k - \text{min_ops}$ 次操作。由于题目要求必须用完恰好 $k$ 次操作，这些剩余的操作必须被“浪费”掉。
- 如何“浪费”操作而不影响最终结果呢？我们可以对同一个字母进行一次往返操作，例如 $'a' \to 'A' \to 'a'$ 。这样的操作消耗 2 次，但字母的最终状态不变。
- 这意味着，所有剩余的操作 $k - \text{min_ops}$ 都必须能这样成对地消耗掉。因此， $k - \text{min_ops}$ 必须是一个非负偶数。
得出可行性条件：综上所述，一个目标大写字母数量 $T$ 是可行的，当且仅当同时满足以下两个条件：
- $k \ge \text{min_ops}$ （总操作次数必须足够）
- $(k - \text{min_ops}) \pmod 2 = 0$ （剩余的操作次数必须是偶数）
寻找最优解：题目要求我们最大化 $T$ 。因此，我们可以从大到小（从 $n$ 到 $0$ ）遍历所有可能的 $T$ 值。第一个满足上述两个条件的 $T$ ，就是我们能得到的最大大写字母数量。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;

    int upper_count = 0;
    // 统计初始大写字母数量
    for (char c : s) {
        if (c >= 'A' && c <= 'Z') {
            upper_count++;
        }
    }

    // 从 n 到 0 遍历所有可能的大写字母目标数量 T
    for (int T = n; T >= 0; --T) {
        // 计算达到目标 T 所需的最小操作次数
        long long min_ops = abs(T - upper_count);
        
        // 检查是否满足两个条件：
        // 1. 总操作次数 k 不少于最小操作次数
        // 2. 剩余的操作次数 (k - min_ops) 是偶数，可以成对抵消
        if (k >= min_ops && (k - min_ops) % 2 == 0) {
            cout << T << endl;
            return;
        }
    }
}

int main() {
    solve();
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        String s = sc.next();

        int upper_count = 0;
        // 统计初始大写字母数量
        for (int i = 0; i < n; i++) {
            if (Character.isUpperCase(s.charAt(i))) {
                upper_count++;
            }
        }

        // 从 n 到 0 遍历所有可能的大写字母目标数量 T
        for (int T = n; T >= 0; T--) {
            // 计算达到目标 T 所需的最小操作次数
            long min_ops = Math.abs(T - upper_count);
            
            // 检查是否满足两个条件：
            // 1. 总操作次数 k 不少于最小操作次数
            // 2. 剩余的操作次数 (k - min_ops) 是偶数，可以成对抵消
            if (k >= min_ops && (k - min_ops) % 2 == 0) {
                System.out.println(T);
                return;
            }
        }
    }
}

def solve():
    n, k = map(int, input().split())
    s = input()

    upper_count = 0
    # 统计初始大写字母数量
    for char in s:
        if 'A' <= char <= 'Z':
            upper_count += 1
    
    # 从 n 到 0 遍历所有可能的大写字母目标数量 T
    for T in range(n, -1, -1):
        # 计算达到目标 T 所需的最小操作次数
        min_ops = abs(T - upper_count)
        
        # 检查是否满足两个条件：
        # 1. 总操作次数 k 不少于最小操作次数
        # 2. 剩余的操作次数 (k - min_ops) 是偶数，可以成对抵消
        if k >= min_ops and (k - min_ops) % 2 == 0:
            print(T)
            return

solve()

算法及复杂度

算法：贪心、枚举
时间复杂度: $O(N)$ ，其中 $N$ 是字符串的长度。统计初始大写字母数量需要 $O(N)$ ，之后从 $n$ 向下遍历寻找可行解最多也需要 $O(N)$ 。
空间复杂度: $O(N)$ ，用于存储输入的字符串。