用排序键同时表达老人优先、年龄降序和登记顺序保持规则。
OJ: noi_openjudge
题目 ID: ch0110-08
难度:入门
标签:排序模拟python
日期: 2026-07-30 23:01
题意
老人（年龄不小于 60 岁）优先看病，老人中年龄大的在前、同龄保持登记顺序；非老人全部保持登记顺序。
思路
保存 (编号, 年龄, 登记顺序)。排序键的第一项 年龄 < 60 对老人是 False、对非老人是 True，所以老人排在前；第二项只有对老人使用 -年龄，让老人年龄降序；最后的登记顺序保证同龄老人和所有非老人都按原顺序排列。
Python 的排序本身稳定，但把登记顺序写进键中能将全部规则明确地表达出来。
代码
Python代码
python
patient_count = int(input())
patients = []
for order in range(patient_count):
patient_id, age = input().split()
age = int(age)
patients.append((patient_id, age, order))
# 年龄不足 60 的人排在后面；同龄老人和所有非老人按登记次序保持稳定。
patients.sort(
key=lambda patient: (
patient[1] < 60,
-patient[1] if patient[1] >= 60 else 0,
patient[2],
)
)
for patient_id, _, _ in patients:
print(patient_id)C++代码
cpp
#include <cstdio>
char id[200][100];
int n;
struct _p {
int id,age,ord;
};
_p p[200];
void init(){
scanf("%d",&n);
int i;
for (i=1;i<=n;i++){
scanf("%s",id[i]);
scanf("%d",&p[i].age);
p[i].id = i;
p[i].ord = i;
}
}
// >=
bool greater(_p &a,_p &b){
if(a.ord == b.ord) return 1;
if( a.age >=60 && b.age < 60)
return 1;
if( a.age >=60 && b.age >=60 ){
if( a.age > b.age)
return 1;
else if ( a.age == b.age)
return a.ord < b.ord;
}
if( a.age < 60 && b.age < 60){
return a.ord < b.ord;
}
return 0;
}
void xchg( _p &a, _p &b){
_p t = a;
a = b;
b = t;
}
void quick_sort(int l,int r){
if( l >= r ) return;
_p key = p[l];
int i= l,j = r;
while(i!= j){
while( i < j && greater(p[j],key))
j--;
while( i < j && greater(key,p[i]))
i++;
if( i < j)
xchg(p[i], p[j]);
}
p[l] = p[i];
p[i] = key;
quick_sort(l, i-1);
quick_sort(i+1, r);
}
int main(){
init();
quick_sort(1, n);
int i;
for(i = n;i>=1;i--)
printf("%s\n",id[ p[i].id ]);
return 0;
}复杂度
时间复杂度为
总结
遇到“优先级 + 保持原顺序”的规则，可将优先级和原始下标依次放入排序键。