题面描述

• 给定只含英文字母的字符串，长度为 $n$。
• 一次操作可以把某个字符在大小写之间切换一次。
• 需要进行恰好 $k$ 次操作，使最终字符串中的大写字母数量尽可能多，输出这个最大数量。

思路

• 设初始大写数量为 $U$，小写数量为 $L=n-U$。

• 优先把小写翻成大写：若 $k\le L$，直接能得到 $U+k$。

• 若 $k>L$，先把全部小写翻为大写得到 $n$，剩余步数 $r=k-L$：

  • 若 $r$ 为偶数，答案为$n$。
  • 若 $r$ 为奇数，必须有一次单翻导致损失 $1$，答案为 $n-1$。

• 综上公式：

  • 若 $k\le L$，答案 $=U+k$；
  • 否则令 $r=k-L$，答案:

  

• 时间复杂度：$O(n)$；空间复杂度：$O(1)$。

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	long long n, k;
	if (!(cin >> n >> k)) return 0;
	string s;
	cin >> s;

	long long U = 0; // 初始大写字母数量
	for (char c : s) {
		if ('A' <= c && c <= 'Z') ++U;
	}
	long long L = n - U; // 初始小写字母数量

	long long ans = 0;
	if (k <= L) {
		// 直接把 k 个小写翻成大写
		ans = U + k;
	} else {
		// 全部小写翻成大写后，剩余步数只影响奇偶
		long long r = k - L;
		if (r % 2 == 0) ans = n;
		else ans = n - 1;
	}
	cout << ans << "\n";
	return 0;
}

Python 实现

import sys

def main():
	data = sys.stdin.read().strip().split()
	if len(data) < 3:
		return
	n = int(data[0])
	k = int(data[1])
	s = data[2]

	U = sum(1 for c in s if 'A' <= c <= 'Z')  # 初始大写数量
	L = n - U  # 初始小写数量

	if k <= L:
		ans = U + k  # 直接翻 k 个小写
	else:
		r = k - L  # 剩余步数
		ans = n if r % 2 == 0 else n - 1  # 看奇偶决定是否损失 1

	print(ans)

if __name__ == "__main__":
	return_code = main()

Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		long k = Long.parseLong(st.nextToken());
		String s = br.readLine();

		long U = 0; // 初始大写数量
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c >= 'A' && c <= 'Z') U++;
		}
		long L = n - U; // 初始小写数量

		long ans;
		if (k <= L) {
			// 直接把 k 个小写翻成大写
			ans = U + k;
		} else {
			// 用掉所有小翻成大写，剩余步数只影响奇偶
			long r = k - L;
			ans = (r % 2 == 0) ? n : (n - 1);
		}
		System.out.println(ans);
	}
}

题目内容

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

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

输入描述

在一行上输入两个整数 $n$ 和 $k(1≤n≤10^5,1≤k≤10^9)$ 。

在一行上输入一个长度为 $n$ ，由大小写字母构成的字符串 $s$ 。

输出描述

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

样例1

输入

1 3
A

输出

0