蓝桥杯15届国赛 最小字符串

题目描述

给定一个长度为 N 且只包含小写字母的字符串 S，和 M 个小写字母 c1,c2,...,cM​。现在你要把 M 个小写字母全部插入到字符串 S 中，每个小写字母都可以插入到任意位置。请问能得到的字典序最小的字符串是什么？
输入格式

第一行包含两个整数 N 和 M。第二行包含一个长度为 N 的字符串 S。第三行包含 M 个小写字母 c1,c2,...,cM。
输出格式

输出一个长度为 N+M 的字符串代表答案。
样例输入 1

1. 4 3
2. abbc
3. cba

复制代码

样例输出 1

1. aabbbcc

复制代码

样例输入 2

1. 7 3
2. lanqiao
3. bei

复制代码

样例输出 2

1. beilanqiao

复制代码

评测用例规模与约定

对于 20% 的评测用例，M=1。
对于 100%的评测用例，1≤N,M≤

。

比较简朴，双指针+sort

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. const int N = 1e5+10;
6. int n, m;
7. char c1[N], c2[N];
9. int main()
10. {
11.         cin>>n>>m;
12.         cin>>c1>>c2;
13.        
14.         sort(c2, c2+m);
15.        
16.         //比较 c1[i] 和 c2[j]，输出较小的字符，并移动相应的指针
17.         int i=0, j=0;
18.         while(i<n && j<m)
19.         {
20.                 if(c1[i] <= c2[j])
21.                 {
22.                         cout<<c1[i];
23.                         i++;
24.                 }
25.                 else
26.                 {
27.                         cout<<c2[j];
28.                         j++;
29.                 }
30.         }
31.        
32.         //如果 c1 或 c2 有剩余未处理的字符，直接按顺序输出
33.         while(i<n)
34.         {
35.                 cout<<c1[i];
36.                 i++;
37.         }
38.         while(j<m)
39.         {
40.                 cout<<c2[j];
41.                 j++;
42.         }
43.        
44.         return 0;
45. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。