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

· · 题解

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

题目传送门

思路

这道题可以通过贪心算法来解决。从左到右遍历字符串，找到第一个 A 和最后一个 B ，将它们消掉，然后继续寻找下一个 A 和 B ，直到无法继续消掉为止。最后剩下的字符数量就是答案。

c++代码

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