2024蓝桥杯国赛B组最小字符串题解：贪心算法实战应用（洛...

19339201706

一、题目解读

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

二、解题思路

采用贪心算法策略：

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

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

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

三、解题步骤

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

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

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

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

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

四、完整代码与注释

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     int N, M;
   
8.     string S, chars;
   
9.    
   
10.     // 读取输入
    
11.     cin >> N >> M;
    
12.     cin >> S;
    
13.     cin >> chars;
    
14.    
    
15.     // 将待插入字符排序，方便贪心选择
    
16.     sort(chars.begin(), chars.end());
    
17.    
    
18.     string result;
    
19.     int charIndex = 0;
    
20.    
    
21.     // 贪心策略：在能保持字典序最小的位置插入当前最小字符
    
22.     for (int i = 0; i < N; ++i) {
    
23.         // 当还有字符可插入，且当前字符比待插入字符大时
    
24.         while (charIndex < M && chars[charIndex] < S[i]) {
    
25.             result.push_back(chars[charIndex]);
    
26.             charIndex++;
    
27.         }
    
28.         result.push_back(S[i]);
    
29.     }
    
30.    
    
31.     // 插入剩余字符
    
32.     while (charIndex < M) {
    
33.         result.push_back(chars[charIndex]);
    
34.         charIndex++;
    
35.     }
    
36.    
    
37.     cout << result << endl;
    
38.     return 0;
    
39. }

复制代码

五、总结

本题通过贪心算法有效解决了最小字符串构造问题，关键在于预处理字符排序和适时插入的策略。算法时间复杂度为O(MlogM + N)，主要消耗在排序环节，整体效率较高。

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