题目传送门
题目分析
本题要求我们判断对于给定的字符串,最少需要多少次字符交换操作,使得字符串中不存在同时包含 LGR 子串和 CSP 子串的情况。每次操作可以交换任意两个字符。
关键观察:
若字符串中不同时存在 LGR 和 CSP 子串,则无需任何操作(答案为 0)
若字符串中同时存在 LGR 和 CSP 子串,则仅需 1 次操作即可满足条件
为什么只需 1 次操作?因为我们可以交换 LGR 中的任意一个字符与 CSP 中的任意一个字符,这样至少会破坏其中一个子串的结构,使得两者无法同时存在。
解题思路
-
统计子串数量:对于每个输入字符串,统计 "LGR" 子串的出现次数(cl)和 "CSP" 子串的出现次数(cC)。
-
判断共存情况:如果两种子串不同时存在,不需要任何操作(操作次数为 0)。
-
计算最小操作次数:若两种子串同时存在,取两者数量的较小值(mv),最小操作次数为 \(⌈min_val / 2⌉\)(即 \((min_val + 1)/ 2\) ,通过整数运算实现向上取整)。
复杂度
时间复杂度:\(O (T×n)\),其中 T 是测试用例数量,n 是字符串长度。对于每个字符串,我们只需遍历一次即可完成检查。
空间复杂度:\(O (1)\),仅使用了常数个额外变量。
代码实现
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;int main() {int AIAmHere = 0;int T;cin >> T;while (T--) {string s;cin >> s;int cl = 0, cC = 0;int n = s.size();for (int i = 0; i <= n - 3; ++i) {string sub = s.substr(i, 3);if (sub == "LGR") {cl++;} else if (sub == "CSP") { cC++;}}int ans = 0;if (cl > 0 && cC > 0) {int mv = min(cl, cC);ans = (mv + 1) / 2; }cout << ans << endl;}return 0;
}
居然真让我找到了可以写题解的红题