2024年蓝桥杯国赛B组最小字符串（洛谷P10910）：贪心算法构造最小字符串

一、问题描述

给定一个长度为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. ‌预处理阶段‌：

• 对待插入字符排序（O(MlogM)时间）

• 确保每次都能取到当前最小的可用字符

2. ‌贪心策略‌：

• 遍历原字符串时，只要当前待插入字符比原字符小就立即插入

• 这种局部最优选择能保证全局最优解

3. ‌边界处理‌：

• 最后需要检查是否还有未插入的字符

• 这些字符直接追加到结果字符串末尾

四、常见问题解答

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

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

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