P9539

zct_sky · 2023-08-15 22:28:43 · 题解

Description

给定一个长度为 n 的字符串，使其将 x 位修改后的字符串字典序最小（n-x \in [l,r]，即 x \in [n-r,n-l]）。

Solution

考虑贪心。

先将该字符串非 a 字符替换成 a，优先从前往后换，若换的个数 = n-l 时，退出循环。

记原字符串所有非 a 字符数为 m，若 m<n-r，则将原字符串中 n-r-m 个 a 字符再替换为 b（若修改非 a 字符为 b，则有效修改数不会增加），优先从后往前换。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return x*y;
}
int n,l,r; 
string s;
bool fuck[1000007];
int main(){
    n=read();l=read();r=read();
    l=n-l;r=n-r;
    cin>>s;
    int flag=0;
    for(int i=0;i<n;i++){
        if(flag==l)break;
        if(s[i]!='a')s[i]='a',flag++;
        else fuck[i]=1;
    }
    if(flag<r){
        for(int i=n-1;i>=0;i--){
            if(fuck[i])s[i]='b',flag++;
            if(flag==r)break;
        }
    }
    cout<<s;
    return 0;
}