csp信奥赛C++高频考点专项训练：【排序算法】案例10：病人排队

csp信奥赛C++高频考点专项训练：【排序算法】案例10：病人排队

题目描述

编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：

输入格式

第

1

1

1 行，输入一个小于

100

100

100 的正整数，表示病人的个数；

后面按照病人登记的先后顺序，每行输入一个病人的信息，包括：一个长度小于

10

10

10 的字符串表示病人的 ID（每个病人的ID各不相同且只含数字和字母），一个整数表示病人的年龄，中间用单个空格隔开。

输出格式

按排好的看病顺序输出病人的 ID，每行一个。

输入输出样例 #1

输入 #1

5
021075 40
004003 15
010158 67
021033 75
102012 30

输出 #1

021033
010158
021075
004003
102012

AC代码

#include<bits/stdc++.h>
using namespace std;

int n; // 病人数量

// 定义病人结构体
struct node{
string id; // 病人ID
int age; // 病人年龄
int num; // 登记顺序编号
}a[110];

// 自定义排序函数
bool cmp(node a, node b){
// 情况1：两人都是老年人（年龄≥60）
if(a.age >= 60 && b.age >= 60){
// 按年龄从大到小排序
if(a.age != b.age)
return a.age > b.age;
// 年龄相同则按登记顺序排序
else
return a.num < b.num;
}
// 情况2：a是老年人，b不是，a排在b前面
else if(a.age >= 60 && b.age < 60){
return true;
}
// 情况3：a不是老年人，b是，b排在a前面
else if(a.age < 60 && b.age >= 60){
return false;
}
// 情况4：两人都不是老年人，按登记顺序排序
else{
return a.num < b.num;
}
}

int main(){
cin >> n; // 输入病人数量

// 读入每个病人的信息
for(int i = 1; i <= n; i++){
cin >> a[i].id >> a[i].age; // 输入ID和年龄
a[i].num = i; // 记录登记顺序
}

// 使用自定义规则排序
sort(a + 1, a + n + 1, cmp);

// 输出排序后的结果
for(int i = 1; i <= n; i++){
cout << a[i].id << endl;
}

return 0;
}

功能分析

核心功能

算法设计

• 数据结构：使用结构体存储病人的ID、年龄和登记序号
• 排序策略：自定义比较函数实现多条件排序
• 稳定性：通过记录登记序号保证相同条件下的稳定排序

关键特点

时间复杂度

• 排序复杂度：O(n log n)
• 空间复杂度：O(n)

完整信奥赛C++普及组CSP-J一等奖通关刷题题单及题解，请关注专栏： https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转 https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解： https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}