自动搬运

查看原文

来自洛谷，原作者为

	Lele_Programmer Ad Astra Per Aspera || F1 车迷 || Love Miku

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

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

以下是正文

P10910 题解

思路

$M$ 个小写字母可以插入到任意位置，说明可以改变顺序，则把字典序更小的放更前面。

先将 $M$ 个小写字母按字典序升序排序，然后两个指针分别指向 $S$ 的开头和 $M$ 个字母中的第 $1$ 个，将字典序更小的一个输出，然后指针往后推一位。

这里要注意了，当两个指针指向的字符字典序相同，只能取字符串 $S$ 中的，因为 $M$ 个字符串的字典序只会递增，而 $S$ 后面可能会出现更小的字符，举个例子，字符串 $S$ 是 ba，而小写字母分别是 bb，答案应该是 babb，而当出现字典序相同的时候取了 $M$ 个字符里面的一个，则答案变成了 bbba。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=100005;

int n,m;
char s[N],arr[N];

int main() {
    scanf("%d %d",&n,&m);
    scanf("%s",s+1);
    scanf("%s",arr+1);
    sort(arr+1,arr+1+m);
    int i=1,j=1;
    while (i<=n+1 || j<=m+1) {
        if (i==n+1 && j==m+1) break;
        if (i==n+1) printf("%c",arr[j++]);
        else if (j==m+1) printf("%c",s[i++]);
        else if (s[i]<=arr[j]) printf("%c",s[i++]);
        else printf("%c",arr[j++]);
    }
    return 0;
}