本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4502 [GESP202603 四级] 礼盒排序 - 洛谷【题目描述】商店推出了许多礼盒每个礼盒中包含k kk件商品每件商品都有一个价格。现在需要对这些礼盒进行排序排序规则如下先按礼盒总价格从小到大排序如果总价格相同按礼盒中最贵商品的价格从小到大排序如果仍然相同按礼盒中最便宜商品的价格从小到大排序如果仍然相同按礼盒编号从小到大排序。请输出排序后的礼盒编号。【输入】第一行包含两个整数n nn和k kk分别表示礼盒数量和每个礼盒中商品的数量。接下来n nn行每行包含k kk个整数第i ii行表示第i ii个礼盒中各商品的价格。【输出】输出一行包含排序后的礼盒编号编号从1 11开始用空格分隔。【输入样例】4 3 3 5 2 4 1 5 2 2 4 3 4 3【输出样例】3 4 2 1【核心思想】问题分析给定n nn个礼盒每个礼盒包含k kk件商品的价格。需要按四重优先级排序礼盒总价格升序 → 最贵商品价格升序 → 最便宜商品价格升序 → 礼盒编号升序。这是一个多关键字自定义排序问题核心在于正确提取每个礼盒的统计特征并按优先级比较。算法选择结构体封装将礼盒的编号、总价格、最大价格、最小价格封装为结构体自定义比较器按四重优先级定义比较函数配合排序算法完成排序关键步骤读入数据读取n , k n, kn,k预处理每个礼盒i ii从1 11到n nn读入k kk个价格同时计算t o t ← tot \leftarrowtot←所有价格之和m a x n ← maxn \leftarrowmaxn←最大价格m i n n ← minn \leftarrowminn←最小价格存储结构体a [ i ] { i , m a x n , m i n n , t o t } a[i] \{i, maxn, minn, tot\}a[i]{i,maxn,minn,tot}自定义排序比较函数c m p cmpcmp若x . t o t ≠ y . t o t x.tot \neq y.totx.toty.tot返回x . t o t y . t o t x.tot y.totx.toty.tot否则若x . m a x n ≠ y . m a x n x.maxn \neq y.maxnx.maxny.maxn返回x . m a x n y . m a x n x.maxn y.maxnx.maxny.maxn否则若x . m i n n ≠ y . m i n n x.minn \neq y.minnx.minny.minn返回x . m i n n y . m i n n x.minn y.minnx.minny.minn否则返回x . i d y . i d x.id y.idx.idy.id输出结果按排序后的顺序输出a [ i ] . i d a[i].ida[i].id时间/空间复杂度时间复杂度O ( n ⋅ k n log ⁡ n ) O(n \cdot k n \log n)O(n⋅knlogn)预处理每个礼盒为O ( k ) O(k)O(k)排序为O ( n log ⁡ n ) O(n \log n)O(nlogn)空间复杂度O ( n ) O(n)O(n)存储n nn个结构体多关键字排序的核心思想统计特征提取在读入时同步计算总价格、最大价格、最小价格避免二次遍历将O ( n ⋅ k ) O(n \cdot k)O(n⋅k)的预处理与读入合并优先级链式比较比较函数按优先级从高到低依次判断高优先级不同时直接返回结果高优先级相同时才比较下一级确保排序结果符合题意稳定排序非必需由于第四优先级是唯一的礼盒编号保证不会出现完全相同的比较结果因此无需稳定排序结构体绑定策略将编号与计算得到的统计量绑定在一起排序后仍能追溯原始身份避免排序后丢失对应关系适用于多维度排序、需要按复合条件排列的自定义排序类问题【算法标签】#普及- #其他排序【代码详解】#includebits/stdc.h// 包含所有标准库头文件usingnamespacestd;// 使用标准命名空间constintN1005;// 定义常量N表示最大学生数量intn,k;// n: 学生数量, k: 每个学生的成绩数量// 定义学生结构体structNode{intid;// 学生编号intmaxn;// 该学生的最高成绩intminn;// 该学生的最低成绩inttot;// 该学生的总成绩}a[N];// 声明结构体数组a用于存储所有学生的信息// 自定义比较函数用于排序boolcmp(Node x,Node y){// 第一优先级按总成绩从小到大排序if(x.tot!y.tot){returnx.toty.tot;}// 第二优先级总成绩相同按最高成绩从小到大排序elseif(x.maxn!y.maxn){returnx.maxny.maxn;}// 第三优先级总成绩和最高成绩都相同按最低成绩从小到大排序elseif(x.minn!y.minn){returnx.minny.minn;}// 第四优先级所有成绩都相同按学号从小到大排序returnx.idy.id;}intmain()// 主函数入口{cinnk;// 输入学生数量n和每个学生的成绩数量k// 读取每个学生的k个成绩for(inti1;in;i){intx;// 临时变量用于读取每个成绩cinx;// 读取第一个成绩intmx,mn,sum0;// mx: 最高成绩, mn: 最低成绩, sum: 总成绩mxmnx;// 初始化最高成绩和最低成绩为第一个成绩sumx;// 将第一个成绩加入总成绩// 读取剩余的k-1个成绩for(intj2;jk;j){cinx;// 读取下一个成绩sumx;// 将成绩加入总成绩// 更新最高成绩if(xmx){mxx;}// 更新最低成绩if(xmn){mnx;}}// 将计算得到的值存入结构体数组a[i].idi;// 学号从1开始的序号a[i].maxnmx;// 最高成绩a[i].minnmn;// 最低成绩a[i].totsum;// 总成绩}// 使用自定义比较函数对数组进行排序// 注意数组下标从1开始所以排序范围是a1到an1sort(a1,an1,cmp);// 输出排序后的学号for(inti1;in;i){couta[i].id ;}coutendl;// 输出换行return0;// 程序正常结束}【运行结果】4 3 3 5 2 4 1 5 2 2 4 3 4 3 3 4 2 1