ARC140B Shorten ARC 题解

思路

我们设奇数次操作为操作1，偶数次操作为操作2，形如 AAAAAAAA...ARCCCCCCC...C 的部分为块（ARC也是块）。

很明显，任何两个块都无法融合（因为一个块中，A不能出现在右边，C不能出现在左边）。

容易发现对于一个块，操作1做完之后，如果左边有A，右边有C则可以继续操作，而操作2操作完之后不能再进行操作，相当于废掉了这个块。

由于每次操作2都会废掉一个块，我们需要考虑废掉那个块。很明显，废掉 “潜力” 最小的块是最优的，同样，操作1操作“潜力”最大的方块是最优的。何为“潜力”，“潜力”就是该块所能进行操作的最多次数（操作1的最多次数），也就是一直对一个块做操作1，能做多少次操作。由于每次操作1都会消耗一个块里的一个A和一个C所以一个块最多能做 $ \min \{$ 块中A的数量 $,$ 块中C的数量 $\}$ 次操作，我们设第 $i$ 个块最多能做 $x_i$ 次操作，那么我们对于每次操作的最优方案为:

• 操作1操作 $\max_{i=1}^{n}{x_i}$
• 操作2操作 $\min_{i=1}^{n}{x_i}$

最后附上代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s;
struct Heap{//找x[i]的最大最小值用堆来实现
    priority_queue<int>q;
    priority_queue<int>d;
    void push(int x){q.push(x);}
    void del(int x){d.push(x);}
    bool empty(){
        while(!d.empty()&&!q.empty()&&q.top()==d.top())q.pop(),d.pop();
        return q.empty();
    }
    int top(){
        while(!d.empty()&&!q.empty()&&q.top()==d.top())q.pop(),d.pop();
        return q.top();
    }
}a,b;
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<n-1;i++){
        if(s[i]!='R'||s[i-1]!='A'||s[i+1]!='C')continue;
        int l=i-1,r=i+1;
        while(l>0&&s[l-1]=='A')l--;
        while(r<n-1&&s[r+1]=='C')r++;
        a.push(min(i-l,r-i));//i-l为块中A的个数，r-i为块中C的个数
        b.push(-min(i-l,r-i));
    }//寻找块
    while(!a.empty()&&!b.empty()){
        if((ans+1)%2){//操作1操作潜力最大的
            int tmp=a.top();
            a.del(tmp);
            b.del(-tmp);
            tmp--;
            if(tmp)a.push(tmp),b.push(-tmp);
        }else{//操作2操作潜力最小的
            int tmp=-b.top();
            a.del(tmp);
            b.del(-tmp);
        }ans++;
    }
    cout<<ans<<endl;
    return 0;
}