题解：P12341 [蓝桥杯 2025 省 A/Python B 第二场] 消消乐

· · 题解

题意分析

根据题目描述，这是一个关于字符串操作的问题，需要通过消去特定字符对（A 在前，B 在后）来最大化剩余字符数量。

思路

注意这题是来最大化剩余字符数量，那我们得想如何贪心使得剩余字符数量最大，也就是消除的字符对最少。 \\

既然要我们使消除的字符对最少，那我们肯定是考虑最不利的情况，由于一定得是 A 在前，B 在后。那如果我们用一个 A 来匹配比较靠后的 B，那么比较前面的 B 就没有前面的 A 来匹配，而比较后面的 A 也失去了本应该匹配的 B。可能这么说有些抽象，那我就举个例子吧。 \\ 示例： \\ 

ABAB

在这个字符串中，如果要使字符全部消除的话那就是 A 和 B 两两一对消除。但我们要使消除的字符对最少，我们可以让第一个 A 和最后一个 B 消除。这样就可以使消除的字符对最少。为什么这个贪心的思路使对的？首先，对于字符串中的每一个 A，既然我们已经枚举到了这一个 A，那前面所有的 A 都一定是用过了的。此时，假设后面还有多余一个的 B，如果我们选择最靠后的 B，那么之后遇到的第一个 B 一定是没的匹配的。这样我们可以使无法匹配的字符数量最大化。或者我们可以从 B 的角度来想，道理也差不多。

\\

所以贪心的依据不就出来了吗？ \\ 既然都已经有思路了，那代码岂不是轻易打出来？

具体实现

由于我们是要枚举最靠前的 A 和最靠后的 B。那我们不妨用一个指针 l 来枚举考前的 A，再用另一个指针枚举靠后的 B。之后不断移动指针 l，直到 s_l=A。当然，r 的移动也是同理。但是，无论如何，一定要满足 l<r，在移动完 l 和 r 后还得加一句特判。然后就是消除一对 A 和 B 了。 \\ 就这样一直循环往复，直到 l\ge r，在循环中统计一共消除了多少对，最后减一减就行啦！

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int l=0,r=s.size()-1,sum=0;
    while(l<r)
     {
        while(s[l]!='A'&&l<r) l++;
        while(s[r]!='B'&&l<r) r--;
        if(l>=r) break;//特判
        l++;r--;sum+=2;
     }
    cout<<s.size()-sum;
    return 0;
}