『FLA - I』歌静河

· · 题解

字符串、贪心

测试点 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;
}