题解：CF2070C Limited Repainting

shiyilang0910 · 2025-03-04 14:39:18 · 题解

思路

本题要使用二分和贪心通过此题。我们可以先二分总惩罚值，再去一遍一遍去找，如果遇到小于等于惩罚值的元素，可以跳过它，因为如果它涂错了也没有关系。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,k,a[300005];
string s;
bool check(int x){//判断是否可行
    string s1="";
    for(int i=0;i<n;i++){
        if (a[i+1]<=x){
            s1+='3';
        }else if (s[i]=='R'){
            s1+='2';
        }else{
            s1+='1';
        }
    }
    int l=0,ans=0;
    while(l<n&&(s1[l]=='2'||s1[l]=='3')){
        l++;
    }
    for(;l<n;){
        while(l<n&&(s1[l]=='1'||s1[l]=='3')){
            l++;
        }
        while(l<n&&(s1[l]=='2'||s1[l]=='3')){
            l++;
        }
        ans++;
    }
    return ans<=k;
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        cin>>s;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        //二分
        int l=0,r=1e9,res=0;
        while(l<=r){
            int mid=(l+r)/2;
            if (check(mid)){//如果可以
                res=mid;//记录答案
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        cout<<res<<endl;//输出
    }
    return 0;//表示完美结束
}