1171 病人排队
大约 3 分钟
1171 病人排队
【算法】 排序、稳定排序
【C++】 stable_sort、结构体、string、cmp 比较函数
【难度】 入门
一、题目简述
病人登记看病,按以下规则排看病顺序:
- 老年人(年龄 ≥ 60)比非老年人优先
- 老年人按年龄从大到小排序,年龄相同按登记先后顺序
- 非老年人按登记先后顺序(即保持输入顺序)
二、解题思路
2.1 关键点:稳定排序
非老年人要保持登记顺序,老年人年龄相同时也保持登记顺序。这本质上需要稳定排序。
C++ 提供了 stable_sort,功能和 sort 相同,但保证相等元素的相对顺序不变。
2.2 排序策略
把所有人放在一个数组中,给每个人记录一个 order(输入序号)。
比较函数:
- 一个老年人、一个非老年人 → 老年人在前
- 两个老年人 → 年龄大的在前(年龄相同则保持输入顺序,由
stable_sort保证) - 两个非老年人 → 保持输入顺序(由
stable_sort保证)
2.3 比较函数写法
bool cmp(Patient a, Patient b) {
// 一个老年一个非老年:老年优先
if (a.isOld != b.isOld)
return a.isOld > b.isOld; // true > false
// 两个都是老年人:按年龄降序
if (a.isOld) // 两个都是老年人
return a.age > b.age;
// 两个都是非老年人:保持原序(stable_sort 自动保证)
return false; // 都"相等"
}注意:这里使用
stable_sort而非sort,因为sort不保证稳定性。
2.4 手动模拟
输入:
5
021075 40
004003 15
010158 67
021033 75
102344 60解析:
| 序号 | ID | 年龄 | 是否老年 |
|---|---|---|---|
| 1 | 021075 | 40 | 否 |
| 2 | 004003 | 15 | 否 |
| 3 | 010158 | 67 | 是 |
| 4 | 021033 | 75 | 是 |
| 5 | 102344 | 60 | 是 |
排序后:
- 老年人先:按年龄降序 → 75(序号4), 67(序号3), 60(序号5)
- 非老年人后:保持原序 → 40(序号1), 15(序号2)
输出:
021033
010158
102344
021075
004003三、参考代码
#include <bits/stdc++.h>
using namespace std;
struct Patient {
string id;
int age;
bool isOld;
};
bool cmp(Patient a, Patient b) {
if (a.isOld != b.isOld)
return a.isOld > b.isOld; // 老年人优先
if (a.isOld)
return a.age > b.age; // 老年人年龄降序
return false; // 非老年人保持原序
}
int main() {
int n;
cin >> n;
Patient a[105];
for (int i = 0; i < n; i++) {
cin >> a[i].id >> a[i].age;
a[i].isOld = (a[i].age >= 60);
}
stable_sort(a, a + n, cmp); // 稳定排序!
for (int i = 0; i < n; i++) {
cout << a[i].id << endl;
}
return 0;
}四、复杂度分析
- 时间复杂度:,
stable_sort的复杂度。 - 空间复杂度:,存储 个病人信息。
五、知识扩展
5.1 sort vs stable_sort
sort | stable_sort | |
|---|---|---|
| 稳定性 | 不稳定 | 稳定 |
| 复杂度 | (额外内存充足时) | |
| 相等元素 | 可能改变相对顺序 | 保持输入顺序 |
什么时候用 stable_sort? 当相等元素需要保持原始顺序时,比如本题中"非老年人按登记顺序"和"同龄老年人按登记顺序"。
5.2 另一种做法:不用 stable_sort
也可以给每个人额外记录一个 order 字段,在 cmp 中显式比较:
bool cmp(Patient a, Patient b) {
if (a.isOld != b.isOld)
return a.isOld > b.isOld;
if (a.isOld && a.age != b.age)
return a.age > b.age;
return a.order < b.order; // 都相等时按输入顺序
}这样用普通 sort 也能达到相同效果,但用 stable_sort 更简洁。
