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

贾蔷
• 阅读 83

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

一、题目解读

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

二、解题思路

采用贪心算法策略:

1.先将待插入字符[排序](https://www.xinaozhilu.cn/tags/14.html),便于按字典序选择

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

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

三、解题步骤

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

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

3.[双指针](https://www.xinaozhilu.cn/tags/7.html)遍历:比较原字符与待插入字符

4.结果构造:按[贪心策略](https://www.xinaozhilu.cn/tags/712.html)构建结果字符串

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

来源:信奥自学之路

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
JavaScript算法系列之
1.输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba字符串拼接(先理解不输入重复字符的)1functionpermutate(str){2varresult;
Wesley13 Wesley13
3年前
HDU 6345(子串查询 暴力)
题意是每组给定一个字符串,在有限查询次数内输出所要查询区间的字典序最小的子串个数。字典序最小的子串,就是所查询区间中字典序最小的单个字符,问题就转化成了求一段区间内字典序最小的字符个数。开始时盲目暴力,直接用桶排序的做法一段一段去求,果然t了(这种就不贴代码了)......然后想到先扫一遍,求出从字符串首位到第i位的最小字符数,再用一个数组存
贾蔷 贾蔷
1个月前
蓝桥杯2023接龙数列(洛谷P9242)题解:动态规划与数字首尾匹配的完美应用
一、题目解读这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列(每个数字的首位等于前一个数字的末位),并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力,是理解数字特征处理和状态转移的典型案例。二、解题步骤1.处理n1的特殊边界情况2.读取输入
贾蔷 贾蔷
1个月前
2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略
一、题目解读2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算
深度学习 深度学习
1个月前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
深度学习 深度学习
1个月前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
深度学习 深度学习
3星期前
动态规划巧解字符串压缩优化问题 - 力扣1531题深度解析
一、问题理解行程长度编码(RunLengthEncoding)是一种简单有效的压缩方法。题目要求我们在删除最多k个字符后,使压缩后的字符串长度最短。二、解题思路1.状态定义:dp:情况1:删除当前字符,直接继承dp1.练习简单DP问题1.逐步过渡到这类复杂
深度学习 深度学习
1星期前
2024年蓝桥杯国赛B组最小字符串(洛谷P10910):贪心算法构造最小字符串
一、问题描述给定一个长度为N的S和M个待插入字符,要求将这些字符全部插入到S中,使得最终形成的字符串最小。二、完整代码解析(含详细注释)Cincludeincludeincludeusingnamespacestd;intmain()intN,M;st
深度学习 深度学习
2天前
洛谷P2758题解:动态规划求解编辑距离的完整攻略
一、题目解读P2758题要求计算两个之间的编辑距离,即通过插入、删除、替换三种操作将字符串A转换为B所需的最小操作次数。题目考察的核心是在中的应用,需要找到最优的路径。二、解题思路采用(DynamicProgramming)策略。核心思想是构建二维dp,d
贾蔷 贾蔷
2天前
力扣15题三数之和解法(C++双指针算法详解)
一、题目解读15题()要求在一个包含n个整数的中,找出所有三个数之和为0的组合,且每个组合的元素不能重复。题目考察数组遍历、与技巧的结合,是经典的多问题,对时间复杂度优化有较高要求。二、解题思路采用“双指针”策略:首先对原数组排序,然后固定第一个数,通过左