一、问题描述

给定一个长度为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;
}

三、算法核心思想

1. ‌预处理阶段‌：
2. • 对待插入字符排序（O(MlogM)时间）
   • 确保每次都能取到当前最小的可用字符
3. ‌贪心策略‌：
4. • 遍历原字符串时，只要当前待插入字符比原字符小就立即插入
   • 这种局部最优选择能保证全局最优解
5. ‌边界处理‌：
6. • 最后需要检查是否还有未插入的字符
   • 这些字符直接追加到结果字符串末尾

四、常见问题解答

Q：为什么需要先排序待插入字符？
A：排序后可以确保每次都能取出当前最小的可用字符，这是贪心策略的关键

Q：如何处理多个相同最小字符的情况？
A：排序后相同字符会相邻，算法会按顺序使用它们

Q：为什么最后要单独处理剩余字符？
A：可能存在所有待插入字符都比原字符串字符小的情况

来源：编程学习