题解：AT_arc140_b [ARC140B] Shorten ARC

Larrylai · 2026-11-10 13:48:47 · 题解

初次思路

首先有一个 naive 的想法，找 R 的左边和右边的连续的 A 和 C 然后进行替换。

但是这个是错误的，在删除的过程中，每一个块最多只能进行两次操作，因为第二次操作会把 R 给删掉，但是这个思路显然是没有考虑到的。

正解思路

可以想到类似田忌赛马的一个东西。

当奇数次操作时，把当前剩下的最长的块去凑操作数，偶数次时，把当前最短的块直接删除。我们发现这其实就是在维护一个集合，奇数次时将最大值减一，偶数次时将最小值删除。

用一个 multiset 维护即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans,cnt=1;
string s;
multiset<int> st;
int check(int x){
    int l=x-1,r=x+1,cnt=0;
    while(l>=1 && r<=n){
        if(s[l]=='A' && s[r]=='C')
            cnt++;
        else
            break;
        l--,r++;
    }
    return cnt;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>s;
    s=" "+s;
    for(int i=1;i<=n;i++)
        if(s[i]=='R')
            if(check(i)>0)
                st.insert(check(i));
    while(!st.empty()){
        if(cnt%2==1){//奇数次操作将最大值减一
            auto it=st.end();
            it--;
            int val=*it;
            st.erase(it);
            if(val-1>0)
                st.insert(val-1);
        }
        else{//偶数次操作找最小的删除
            auto it=st.begin();
            st.erase(it);
        }
        ans++,cnt++;
    }
    cout<<ans;
    return 0;
}