自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:17:27，当前版本为作者最后更新于2025-06-24 13:57:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心。

把 $\texttt{A,B,C}$ 的位置存下来，然后对于每一个 $\texttt{A}$ 找目前还没删掉的最后的 $\texttt{B}$，对于每一个 $\texttt{C}$ 找目前还没删掉的最前的 $\texttt{B}$ 就行了。

$\texttt{A}$ 要倒序删除，$\texttt{C}$ 则正序。

正确性大概就是注意到 $\texttt{AB,BC}$ 的贡献权值没有什么差异，所以先后考虑顺序是任意的，然后就是要尽可能的把难以删除的先删去，于是有了删除顺序。

做完了。

#include<bits/stdc++.h>
using namespace std;
stack<int>A;
queue<int>C;
deque<int>B;
int ans;
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
        if(s[i]=='C')C.push(i);
    for(int i=0;i<s.size();i++)
        if(s[i]=='B')B.push_back(i);
    for(int i=0;i<s.size();i++)
        if(s[i]=='A')A.push(i);
    while(!A.empty()&&!B.empty()){
        if(A.top()<B.back())B.pop_back(),ans++;
        A.pop();
    }
    while(!C.empty()&&!B.empty()){
        if(C.front()>B.front())B.pop_front(),ans++;
        C.pop();
    }
    cout<<ans;
    return 0;
}

机房键盘怎么这么难用啊。