蓝桥杯算法精讲：贪心算法的简单应用与题解

目录前言一、贪心算法1.1 简单贪心1.1.1 货舱选址1.1.2 最大子段和1.1.3 纪念品分组1.1.4 排座椅1.1.5 矩阵消除游戏结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、贪心算法贪心算法是两极分化很严重的算法。简单的问题会让你觉得理所应当难一点的问题会让你怀疑人生。1什么是贪心算法?贪心算法或者说是贪心策略企图用局部最优找出全局最优。把解决问题的过程分成若干步解决每一步时都选择”当前看起来最优的”解法希望”得到全局的最优解。2.贪心算法的特点对于大多数题目贪心策略的提出并不是很难难的是证明它是正确的。因为贪心算法相较于暴力枚举每一步并不是把所有情况都考虑进去而是只考虑当前看起来最优的情况。但是局部最优并不等于全局最优所以我们必须要能严谨的证明我们的贪心策略是正确的。一般证明策略有反证法数学归纳法交换论证法等等。当问题的场景不同时贪心的策略也会不同。因此贪心策略的提出是没有固定的套路和模板的。我后面讲的题目虽然分类但是大家会发现具体的策略还是相差很大。因此不要妄想做几道贪心题目就能遇到一个会一个。有可能做完50道贪心题目之后第51道还是没有任何思路。3. 如何学习贪心?先有一个认知做了几十道贪心的题目遇到一个新的又没有思路这时很正常的现象把心态放平。前期学习的时候重点放在各种各样的策略上把各种策略当成经验来吸收在平常学习的时候尽可能的证明一下这个贪心策略是否正确这样有利于培养严谨的思维。但是在比赛中能想出来一个策略就已经不错了如果再花费大量的时间去证明有点得不偿失。这个时候如果根据贪心策略想出来的若干个边界情况都能过的话就可以尝试去写代码了。1.1 简单贪心1.1.1 货舱选址货舱选址这里提供两种写法直接法排序后取中位数计算所有点到中位数的绝对距离之和。#includeiostream#includealgorithmusingnamespacestd;typedeflonglongLL;constintN1e510;intn;LL a[N];intmain(){cinn;for(inti1;in;i)cina[i];sort(a1,a1n);LL ret0;// 利用中间值来计算// for(int i 1; i n; i)// {// ret abs(a[i] - a[(n 1) / 2]);// }// 用结论计算for(inti1;in/2;i){reta[n-i1]-a[i];}coutretendl;return0;}配对法排序后首尾配对第i个和第n-i1个累加每对的差值结果与直接法完全一致每对差值等于它们到中位数的距离之和。#includeiostream#includealgorithmusingnamespacestd;constintN1e510;typedeflonglongLL;LL a[N];LL n;intmain(){cinn;for(inti1;in;i)cina[i];sort(a1,an1);//利用结论配对法LL ret0;for(inti1;i(n/2);i){retabs(a[n1-i]-a[i]);}coutretendl;return0;}题目中数据范围为什么定义为long long分两种极端情况① 直接法算所有点到中位数的距离和最坏情况所有商店都分布在数轴两端比如一半在 0一半在 40000中位数在中间。那每个点到中位数的距离最大约等于 40000。总距离和 ≈ 105×400004×109这个数远大于int 的最大值 2.1×109int 根本存不下会直接溢出。② 配对法首尾配对算差值和排序后把第 i 个和第 n-i1 个配对每对差值是 大坐标 - 小坐标。最坏情况最小坐标是 0最大是 40000每对差值都是40000。配对数 ≈ N/25×104总距离和 ≈ 5×104×400002×109这个数虽然比 2.1×109小一点但非常接近上限如果 N 是奇数比如 1051配对数会更多总和就会超过 int 上限依然有溢出风险。在蓝桥杯比赛中很多数据范围溢出的情况都是隐性的新手建议直接全部的定义为long long更为稳妥。1.1.2 最大子段和最大子段和解法有没有似曾相识的感觉这是我们第二次遇见它了但还不是最后一次~贪心算法从前往后累加我们会遇到下面两种情况目前的累加和≥0那么当前累加和还会对后续的累加和做出贡献那我们就继续向后累加然后更新结果目前的累加和0对后续的累加和做不了一点贡献直接大胆舍弃计算过的这一段把累加和重置为0然后继续向后累加。这样我们在扫描整个数组一遍之后就能更新出最大子段和。聪明的你此时就会有「些」大大的疑惑了whywhywhy为什么可以得到「最优解」怎么感觉这个策略是「错」的啊感觉「好多情况」都没考虑进去为什么就得到一个正确的结果为什么可以「大胆舍去」这一段累加和如果你有大大的疑惑这就对了。我刚开始做这道题看到别人的题解是这样写的时候也有如此疑惑。我觉得这就是贪心算法的魅力吧看似很简单很玄学其实有很多值的我们思考的地方别着急我们接下来证明一下这个贪心策略是正确的。其实只需要证明我们在累加的过程中出现负数时为什么可以大胆的舍去这一段区间然后重新开始。证明以下三点就可以「大胆舍弃」了在累加的过程中算出一段区间和sum[ab]0如果不舍弃这一段那么[ab]段之间就会存在一点「以某个位置为起点」就会「更优」分为下面两种情况1.在ab段存在一个点c从这个位置开始「越过b」的累加和比从a开始的累加和更优用「反证法」证明这种情况不存在。如果存在这一点那么sum[c,b] sum[a,b]这样才能保证向后加的时候更优。但这是「不可能」的。如果sum[c,b] sum[a,b]那么sum[a,c一1] 0这与我们的贪心策略矛盾。因为我们贪心策略向后加的时候只要不小于0就会一直加下去。如果[ac一1]段小于0就会在c点之前停止不会累加到b。因此区间内不存在一点在计算子数组和时在越过的情况下能比从a开始更优。2.在ab段存在一个点c从这个位置开始「不越过b」的累加和比从a开始的累加和更优也可以用「反证法」证明这种情况不存在。如果存在这一点那么sum[c,k] sum[a,k]。但这是不可能的。如果sum[c,k] sum[a,k]那么sum[a,c一1] 0这与我们的贪心策略矛盾。因此区间内不存在一点在计算子数组和时在「不越过b」的情况下能比从a开始更优。综上所述我们可以大胆舍弃这一段重新开始。#includeiostreamusingnamespacestd;typedeflonglongLL;constintN2e510;intn;LL a[N];intmain(){cinn;for(inti1;in;i)cina[i];LL sum0,ret-1e6;for(inti1;in;i){suma[i];retmax(ret,sum);if(sum0)sum0;}coutretendl;return0;}要点补充ret用来统计最终结果但是有可能整个数组全是负数最后结果应该是当中最大的那个值所以ret不能初始化为0要初始化为一个特别小的数1.1.3 纪念品分组纪念品分组【解法】先将所有的纪念品排序每次拿出当前的最小值与最大值y如果 x y ≤ w就把这两个放在一起;如果 x y w说明此时最大的和谁都凑不到一起y 单独分组x 继续留下在进行下一次判断。直到所有的物品都按照上述规则分配之后得到的组数就是最优解。#includeiostream#includealgorithmusingnamespacestd;constintN3e410;typedeflonglongLL;LL a[N];LL w,n;intmain(){cinwn;for(inti1;in;i)cina[i];sort(a1,an1);LL l1,rn,ret0;//两个指针相遇时当前的物品也需要分组while(lr){//如果if else中需要执行两个语句两个语句之间一定要用逗号隔开if(a[l]a[r]w)l,r--;//r单独放elser--;ret;}coutretendl;return0;}1.1.4 排座椅排座椅核心目标是在 M 行 N 列的教室中选择 K 个横向通道行与行之间和 L 个纵向通道列与列之间使得被通道隔开的交头接耳同学对数最多即剩余交头接耳对数最少。贪心策略每个候选通道位置行 i 与 i1 之间、列 j 与 j1 之间的「价值」 在此处开通道能隔开的交头接耳对数。我们只需选择价值最高的 K 个横向通道和价值最高的 L 个纵向通道即可得到最优解。#includeiostream#includealgorithmusingnamespacestd;constintN1010;structnode{intindex;// 通道位置编号行/列intcnt;// 此位置作为通道能隔开的交头接耳对数}row[N],col[N];// row: 横向通道数组col: 纵向通道数组intm,n,k,l,d;// 输入参数行数、列数、横向通道数、纵向通道数、交头接耳对数// 按 cnt 从大到小排序用于筛选价值最高的通道boolcmp1(nodex,nodey){returnx.cnty.cnt;}// 按 index 从小到大排序用于输出时保证顺序递增boolcmp2(nodex,nodey){returnx.indexy.index;}intmain(){cinmnkld;// 初始化给每个通道位置赋予对应的编号for(inti1;im;i)row[i].indexi;for(inti1;in;i)col[i].indexi;// 统计每个通道的价值cntwhile(d--){intx,y,p,q;cinxypq;if(xp)// 左右相邻同一行→ 对应纵向通道col[min(y,q)].cnt;else// 前后相邻同一列→ 对应横向通道row[min(x,p)].cnt;}// 第一步按价值降序排序筛选出价值最高的K/L个通道sort(row1,row1m,cmp1);sort(col1,col1n,cmp1);// 第二步将筛选出的通道按位置升序排序保证输出顺序sort(row1,row1k,cmp2);sort(col1,col1l,cmp2);// 输出结果for(inti1;ik;i)coutrow[i].index ;coutendl;for(inti1;il;i)coutcol[i].index ;coutendl;return0;}尤其要注意这里 sort 需要的是告诉它 “用哪个函数做比较”把函数本身传过去由 sort 内部自己去调用所以只需要写 cmp1函数名即可不用加括号和参数。1.1.5 矩阵消除游戏矩阵消除游戏题目核心思路我们有一个 n×m 的矩阵最多进行 k 次操作每次选择一行或一列将其全部置 0并获得该行 / 列所有元素的和作为分数。目标是最大化总得分。由于 n, m ≤ 15直接暴力枚举所有行 列的选择组合会超时2^(nm) 量级因此代码采用枚举行的选择 贪心选列的优化思路先枚举所有可能的行选择方案用二进制掩码表示确定要消除哪些行。对于剩下未被消除的行计算每一列的和然后贪心选择前k - 选中行数个最大的列和补全 k 次操作。遍历所有行选择方案取总分最大值。#includeiostream#includealgorithm#includecstringusingnamespacestd;constintN20;intn,m,k;inta[N][N];intcol[N];// 统计列和// 统计 x 的二进制表示中 1 的个数intcalc(intx){intret0;while(x){ret;x-x-x;}returnret;}// 按照值从大到小排序boolcmp(inta,intb){returnab;}intmain(){cinnmk;for(inti0;in;i)for(intj0;jm;j)cina[i][j];intret0;// 暴力枚举出行的所有选法for(intst0;st(1n);st){intcntcalc(st);if(cntk)continue;// 不合法的状态memset(col,0,sizeofcol);intsum0;// 记录当前选法中的和for(inti0;in;i){for(intj0;jm;j){if((sti)1)suma[i][j];elsecol[j]a[i][j];}}// 处理列sort(col,colm,cmp);// 选 k - cnt 列for(intj0;jk-cnt;j)sumcol[j];retmax(ret,sum);}coutretendl;return0;}1. 常量与变量定义constintN20;// 数组最大维度题目n/m≤1520足够intn,m,k;// n行、m列、最多k次操作inta[N][N];// 存储矩阵的原始数值intcol[N];// 核心辅助数组记录「未被选中的行」中每一列的元素和变量作用a[i][j]第 i 行第 j 列的原始值i/j 从 0 开始代码用 0 索引col[j]所有没被选中消除的行中第 j 列的元素总和后续用来选列得分。2. calc 函数统计二进制中 1 的个数核心工具函数// 统计 x 的二进制表示中 1 的个数intcalc(intx){intret0;// 计数1的个数while(x)// x0时循环{ret;// 每找到一个1计数1x-x-x;// 核心操作消去x最右侧的1}returnret;}核心原理x -x 是计算机中快速找「最右侧 1」的位运算技巧补码特性。例x6二进制 110→ x-x2二进制 010→ x - 2 后变为 4二进制 100再循环x4 → x-x4 → x -4 后变为 0循环结束ret26 的二进制有 2 个 1。函数作用输入一个二进制数行选择掩码返回「选中的行数」因为掩码中 1 的位置对应选中的行。3. cmp 函数排序比较器// 按照值从大到小排序boolcmp(inta,intb){returnab;}作用给 sort 函数用让数组降序排列默认 sort 是升序。例col [10,5,20] → 调用 sort(col, col3, cmp) 后变为 [20,10,5]。主函数核心逻辑分 8 步拆解intmain(){// 步骤1输入矩阵维度、操作次数、矩阵元素cinnmk;for(inti0;in;i)for(intj0;jm;j)cina[i][j];// 步骤2初始化全局最大得分intret0;// 步骤3枚举所有行的选择方案二进制掩码// 1n 等价于 2^nst的取值范围0 ~ 2^n -1for(intst0;st(1n);st){// 步骤4计算当前方案选中的行数跳过不合法方案intcntcalc(st);// cnt 选中的行数if(cntk)continue;// 选中行数超过k无法再选列直接跳过// 步骤5重置col数组为0计算行得分未选行的列和memset(col,0,sizeofcol);// 每次枚举新方案col要清零intsum0;// 记录当前方案的总得分for(inti0;in;i)// 遍历每一行{for(intj0;jm;j)// 遍历每一列{// 判断第i行是否被选中st的第i位是否为1if((sti)1){// 情况1第i行被选中 → 累加该行第j列的值到sum行得分suma[i][j];}else{// 情况2第i行未被选中 → 累加该值到col[j]后续列得分用col[j]a[i][j];}}}// 步骤6贪心选列补全k次操作sort(col,colm,cmp);// 列和降序排列// 选 k - cnt 个最大的列和剩余操作次数for(intj0;jk-cnt;j){sumcol[j];}// 步骤7更新全局最大得分retmax(ret,sum);}// 步骤8输出最终结果coutretendl;return0;}关键步骤的「具象化例子」假设n2行m2列k2矩阵为a[0][0]1,a[0][1]2第0行和为3 a[1][0]3,a[1][1]4第1行和为7枚举 st1二进制 01st1 → 二进制 01 → 第 0 行被选中i0 时(10)11第 1 行未被选中i1 时(11)10cntcalc(1)1≤k2合法计算 sum 和 coli0选中行j0 → sum 1j1 → sum 2 → sum3i1未选中行j0 → col [0] 3j1 → col [1] 4 → col[3,4]排序 col降序后 [4,3]剩余操作次数k-cnt1 → 选 col [0]4 → sum347ret 更新为 7初始 ret0。枚举 st2二进制 10st2 → 第 1 行被选中第 0 行未被选中cnt1sum7第 1 行和col[1,2]排序后 col[2,1]选 1 个 → sum729ret 更新为 9。枚举 st3二进制 11st3 → 两行都被选中cnt2sum3710剩余操作次数 0 → 不选列ret 更新为 10最终结果。最后的最后还没有结束该题目还存在一个隐性的bug我也是刚刚不经意间测了出来若全局变量 col[N] 定义在 a[N][N] 之前提交代码就不能通过示例了按照常理来说全局变量的定义顺序不应该影响最终结果才是原因出在// 选 k - cnt 个最大的列和剩余操作次数for (int i 0; i k - cnt; i) sum col[i];i k - cnt会发生越界访问的情况k的数据范围是很大的k n * mk最大可以把整个矩阵所有的数选到就是如果cnt很小为0/1k很大n×m在这一列选的时候就会超过这一列的极限这一列的极限为m个发生越界访问为了避免发生这种风险就可以使用下面的写法// 选 k - cnt 个最大的列和剩余操作次数for(intj0;jmin(k-cnt,m);j)sumcol[j];若k - cnt过于大的时候就强制把范围限制在所有的列m先定义a数组再定义col数组没有出错的原因是后定义的col数组即使越界访问也是访问那些没有定义的格子全局变量后面没有定义的格子值是0所以后面sum累加的时候也不会出错但是若先定义col数组再定义a数组两个数组在内存中存储的时候就是挨着存的此时col数组越界的时候就会访问到a数组a数组中的值就不是0了所以后续累加会出错结语