2024蓝桥杯国赛B组最小字符串题解：贪心算法实战应用（洛谷P10910代码解析）

一、题目解读

题目要求给定一个长度为N的字符串S和M个待插入字符，通过将这些字符全部插入S中，构造出字典序最小的新字符串。这是典型的字符串构造问题，考察选手对贪心算法的理解和应用能力。

二、解题思路

采用贪心算法策略：

    1.先将待插入字符排序，便于按字典序选择

    2.遍历原字符串时，在保证字典序最小的位置插入当前最小的可用字符

    3.最后处理剩余未插入字符

三、解题步骤

    1.输入处理：读取N,M,S和字符集

    2.字符排序：预处理待插入字符

    3.双指针遍历：比较原字符与待插入字符

    4.结果构造：按贪心策略构建结果字符串

    5.剩余处理：追加剩余字符

四、完整代码与注释

#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 + N)，主要消耗在排序环节，整体效率较高。