自动搬运

查看原文

来自洛谷，原作者为

	ScaredQiu Life Still Left In Me

搬运于2025-08-24 23:01:42，当前版本为作者最后更新于2024-02-25 22:40:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

字符串、贪心

测试点 $1 \sim 3$

观察发现先替换掉 $a$ 中所有 #，再替换掉 $b$ 中所有 # 得到的 $a$ 字典序最小。

测试点 $4 \sim 6$

由于只有一个串里有 #，操作顺序是唯一的，执行完 $m$ 次操作后输出 $a$ 即可。

测试点 $7 \sim 10$

为了最小化字典序，应该尽量将 $a$ 中靠前的 # 替换成 a。依次考虑每个 #，假设当前操作中用来替换 # 的字符是 y，如果 $b$ 中剩余的 # 的数量能够进行两次操作，那么就对 $b$ 进行两次操作，再使用 a 替换 $a$ 中的 #。

只考虑 a 的原因是如果能通过对 $b$ 进行若干次操作将当前字符换成 b，那么可以通过减少一次操作将当前字符变成 a，这样不仅会让 $a$ 的字典序更小，还留出了更多的操作，显然是不劣的。

对于 $a$ 中的每个 #，考虑是否能通过对 $b$ 操作将用来替换的字符换成 a，如果能则进行操作。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
string a,b;
char s;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>a>>b,s='a';
    for(int i=0;i<=n-1;i++) if(b[i]=='#') cnt++;
    for(int i=0;i<=n-1;i++) if(a[i]=='#'){
        if(s!='a'&&cnt>='z'-s+1) cnt-='z'-s+1,s='a';
        a[i]=s,s=s=='z' ? 'a':s+1;
    }
    cout<<a<<'\n';
    return 0;
}