【蓝桥杯 / 算法题解22】超级计算机（贪心算法 + 多关键字排序）

题目大意：nnn个科研人员需要使用一台超级计算机，每个人所需的使用时长不同。请安排一个使用顺序，使得所有人的平均等待时间（即所有人总等待时间之和）最短。如果存在多种使总时间最短的方案，原始编号较小的人优先排在前面。

💡 一、 题目核心思路解析

这道题是经典的“排队打水问题” / “接水问题”模型，核心考点在于贪心算法（Greedy Algorithm）以及自定义多关键字排序。

1. 为什么“耗时短的优先”能使总时间最短？（贪心证明）

假设有nnn个人，第iii个人所需的时间为TiT_iTi​：

• 第 1 个人完成时，所有人（包括他自己）一共经历了T1T_1T1​的等待时长（占用系数为nnn）。
• 第 2 个人完成时，后面所有剩余的人都额外经历了T2T_2T2​的等待时长（占用系数为n−1n-1n−1）。
• …
• 第iii个人对总等待时间的贡献为：Ti×(n−i+1)T_i \times (n - i + 1)Ti​×(n−i+1)。

公式表达：
Total Time=T1×n+T2×(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 Time=T1​×n+T2​×(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 开始）升序排列。

🛠️ 二、 数据结构与算法选择

1. 结构体（struct）绑定数据：由于排序后会打乱原始位置，我们需要一个结构体把每个人的id（原始编号）和time（计划时长）绑定在一块。
2. 自定义比较函数（cmp）：
   • 优先比较time（按使用时间升序）；
   • 若time相同，则比较id（按原始编号升序）。
3. 复杂度分析：
   • 时间复杂度：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++ 满分示范代码

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;// 定义科研人员结构体structPerson{intid;// 原始编号 (1-based)inttime;// 使用时长};// 自定义多关键字排序比较函数boolcmp(constPerson&a,constPerson&b){if(a.time!=b.time){returna.time<b.time;// 1. 时长短的优先}returna.id<b.id;// 2. 时长相同时，编号小的优先}intmain(){// 优化 I/O 读写性能ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cin>>n))return0;vector<Person>p(n);for(inti=0;i<n;i++){p[i].id=i+1;// 存储 1 到 n 的原始编号cin>>p[i].time;}// 执行多关键字排序sort(p.begin(),p.end(),cmp);// 输出最优解的编号顺序for(inti=0;i<n;i++){cout<<p[i].id<<(i==n-1?"":" ");}cout<<"\n";return0;}

📝 四、 总结与避坑指南

1. 不要丢掉原始编号：如果只对纯数字数组排序，会丢失题目要求的“输出原编号”信息，因此必须使用结构体（struct）或std::pair<int, int>。
2. 注意平局逻辑：一定要在比较函数cmp里写上a.id < b.id的次要判断，否则遇到相同耗时的数据时会因为乱序而导致 WA（Wrong Answer）。
3. 输出格式处理：末尾空格格式控制（如i == n - 1 ? "" : " "），保持良好的代码规范。