2024蓝桥杯国赛B组最小字符串题解：贪心算法实战应用（洛...
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506071749309848378137.jpg一、题目解读题目要求给定一个长度为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 < S) {
result.push_back(chars);
charIndex++;
}
result.push_back(S);
}
// 插入剩余字符
while (charIndex < M) {
result.push_back(chars);
charIndex++;
}
cout << result << endl;
return 0;
}
五、总结本题通过贪心算法有效解决了最小字符串构造问题，关键在于预处理字符排序和适时插入的策略。算法时间复杂度为O(MlogM + N)，主要消耗在排序环节，整体效率较高。参考：2024蓝桥杯国赛B组最小字符串题解：贪心算法实战应用（洛谷P10910代码解析）
页:
[1]