题解：P12690 [KOI 2022 Round 1] ABBC

· · 题解

一道贪心题。

题意

两种操作：

换一个角度想，在序列里找一个 B，与它前面的 A 或后面的 C 匹配并删除。

思路

从左往右找，每找到一个 B，匹配之后的距离它最近的一个 C，若没有则匹配一个前面的 A。

贪心正确性

由于每一个点只能被删一次，能匹配就匹配肯定是最优的。可以发现，能匹配的 A 是越来越多的，而 C 是越来越少的，所以优先匹配 C。又因为距离越近的 C 失效得越快，所以优先匹配距离近的 C。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
long long n,ans,a,c,lst,nxt[maxn];
//a表示有多少A可以匹配，c表示最近能匹配的C的坐标
bool b[maxn];
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='C')
        {
            if(lst==0)c=i;
            else nxt[lst]=i;
            lst=i;
        }
    }
    for(int i=1;i<=n;i++)
    if(b[i]==0)
    {
        if(s[i]=='A')a++;
        else if(s[i]=='B')
        {
            if(c!=0)
            {
                b[c]=1;
                c=nxt[c];//找下一个C
                ans++;
            }
            else if(a>0)
            {
                a--;
                ans++;
            }
        }
        else c=nxt[c];//当前位置的C已经失效了，换到下一位的C
    }
    cout<<ans;
}