【蓝桥杯 / 算法题解22】超级计算机贪心算法 多关键字排序题目大意nnn个科研人员需要使用一台超级计算机每个人所需的使用时长不同。请安排一个使用顺序使得所有人的平均等待时间即所有人总等待时间之和最短。如果存在多种使总时间最短的方案原始编号较小的人优先排在前面。 一、 题目核心思路解析这道题是经典的“排队打水问题” / “接水问题”模型核心考点在于贪心算法Greedy Algorithm以及自定义多关键字排序。1. 为什么“耗时短的优先”能使总时间最短贪心证明假设有nnn个人第iii个人所需的时间为TiT_iTi​第 1 个人完成时所有人包括他自己一共经历了T1T_1T1​的等待时长占用系数为nnn。第 2 个人完成时后面所有剩余的人都额外经历了T2T_2T2​的等待时长占用系数为n−1n-1n−1。…第iii个人对总等待时间的贡献为Ti×(n−i1)T_i \times (n - i 1)Ti​×(n−i1)。公式表达Total TimeT1×nT2×(n−1)T3×(n−2)⋯Tn×1 \text{Total Time} T_1 \times n T_2 \times (n - 1) T_3 \times (n - 2) \dots T_n \times 1Total TimeT1​×nT2​×(n−1)T3​×(n−2)⋯Tn​×1为了让Total Time\text{Total Time}Total Time最小我们需要将耗时最少TiT_iTi​最小的人放在最前面使其被乘以最大的系数nnn将耗时最长的人放在最后面被乘以最小的系数111。2. 打破平局规则Tie-Breaking题目中有一个非常关键的约束细节“如果存在平均等待时间相同的两个顺序编号较小的人优先排在前面。”这意味着当两个人所需的使用时间TiT_iTi​相等时我们需要按照他们的原始编号ididid从 1 开始升序排列。️ 二、 数据结构与算法选择结构体struct绑定数据由于排序后会打乱原始位置我们需要一个结构体把每个人的id原始编号和time计划时长绑定在一块。自定义比较函数cmp优先比较time按使用时间升序若time相同则比较id按原始编号升序。复杂度分析时间复杂度O(Nlog⁡N)O(N \log N)O(NlogN)主要耗时在std::sort排序上。面对N≤105N \le 10^5N≤105的数据量可以在 10ms 内秒杀。空间复杂度O(N)O(N)O(N)用于开辟结构体数组存储数据。 三、 C 满分示范代码#includeiostream#includevector#includealgorithmusingnamespacestd;// 定义科研人员结构体structPerson{intid;// 原始编号 (1-based)inttime;// 使用时长};// 自定义多关键字排序比较函数boolcmp(constPersona,constPersonb){if(a.time!b.time){returna.timeb.time;// 1. 时长短的优先}returna.idb.id;// 2. 时长相同时编号小的优先}intmain(){// 优化 I/O 读写性能ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorPersonp(n);for(inti0;in;i){p[i].idi1;// 存储 1 到 n 的原始编号cinp[i].time;}// 执行多关键字排序sort(p.begin(),p.end(),cmp);// 输出最优解的编号顺序for(inti0;in;i){coutp[i].id(in-1?: );}cout\n;return0;} 四、 总结与避坑指南不要丢掉原始编号如果只对纯数字数组排序会丢失题目要求的“输出原编号”信息因此必须使用结构体struct或std::pairint, int。注意平局逻辑一定要在比较函数cmp里写上a.id b.id的次要判断否则遇到相同耗时的数据时会因为乱序而导致 WAWrong Answer。输出格式处理末尾空格格式控制如i n - 1 ? : 保持良好的代码规范。