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

胡志明t

一、问题描述

给定一个长度为N的字符串S和M个待插入字符，要求将这些字符全部插入到S中，使得最终形成的字符串字典序最小。

二、完整代码解析（含详细注释）

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)时间）
  • 确保每次都能取到当前最小的可用字符
    
    

• ‌贪心策略‌：

  
  
  • 遍历原字符串时，只要当前待插入字符比原字符小就立即插入
  • 这种局部**选择能保证全局**解
    
    

• ‌边界处理‌：

  
  
  • **需要检查是否还有未插入的字符
  • 这些字符直接追加到结果字符串末尾
    
    

四、常见问题解答

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

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

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

来源：编程学习