自动搬运

查看原文

来自洛谷，原作者为

	zct_sky sto @jxbe6666 orz || 再起不能

搬运于2025-08-24 22:49:21，当前版本为作者最后更新于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;
}