一、问题描述
给定一个长度为N的字符串S和M个待插入字符，要求将这些字符全部插入到S中，使得最终形成的字符串字典序最小。
二、完整代码解析（含详细注释）
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int N, M;
string S, chars;
// 读取输入
cin >> N >> M;
cin >> S;
cin >> chars;
// 将待插入字符排序，方便贪心选择
sort(chars.begin(), chars.end());
string result;
int charIndex = 0;
// 贪心策略：在能保持字典序最小的位置插入当前最小字符
for (int i = 0; i < N; ++i) {
// 当还有字符可插入，且当前字符比待插入字符大时
while (charIndex < M && chars[charIndex] < S[i]) {
result.push_back(chars[charIndex]);
charIndex++;
}
result.push_back(S[i]);
}
// 插入剩余字符
while (charIndex < M) {
result.push_back(chars[charIndex]);
charIndex++;
}
cout << result << endl;
return 0;
}三、算法核心思想
- 预处理阶段：
- 对待插入字符排序（O(MlogM)时间）
- 确保每次都能取到当前最小的可用字符
- 贪心策略：
- 遍历原字符串时，只要当前待插入字符比原字符小就立即插入
- 这种局部最优选择能保证全局最优解
- 边界处理：
- 最后需要检查是否还有未插入的字符
- 这些字符直接追加到结果字符串末尾
四、常见问题解答
Q：为什么需要先排序待插入字符？
A：排序后可以确保每次都能取出当前最小的可用字符，这是贪心策略的关键
Q：如何处理多个相同最小字符的情况？
A：排序后相同字符会相邻，算法会按顺序使用它们
Q：为什么最后要单独处理剩余字符？
A：可能存在所有待插入字符都比原字符串字符小的情况
来源：编程学习
