题解：P12672 「LAOI-8」近期我们注意到有网站混淆视听

· · 题解

题目传送门

题目分析

本题要求我们判断对于给定的字符串，最少需要多少次字符交换操作，使得字符串中不存在同时包含 LGR 子串和 CSP 子串的情况。每次操作可以交换任意两个字符。

关键观察：

若字符串中不同时存在 LGR 和 CSP 子串，则无需任何操作（答案为 0）
若字符串中同时存在 LGR 和 CSP 子串，则仅需 1 次操作即可满足条件

为什么只需 1 次操作？因为我们可以交换 LGR 中的任意一个字符与 CSP 中的任意一个字符，这样至少会破坏其中一个子串的结构，使得两者无法同时存在。

解题思路

  1. 统计子串数量：对于每个输入字符串，统计 "LGR" 子串的出现次数（cl）和 "CSP" 子串的出现次数（cC）。

  2. 判断共存情况：如果两种子串不同时存在，不需要任何操作（操作次数为 0）。

  3. 计算最小操作次数：若两种子串同时存在，取两者数量的较小值（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;
}

居然真让我找到了可以写题解的红题