P4616 病人排队（基础）

解题思路

这道题就像医院急诊室分诊，病人按轻重缓急排队，规则分三条。我们分四步来解决。

第一步，把排队规则梳理清楚。 老年人（年龄大于等于 60 岁）优先，插到最前面看诊；老年人之间按年龄从大到小排，年龄相同再按登记顺序排；非老年人之间完全按登记顺序排，谁先来谁先看。

第二步，用结构体把信息装好。 用结构体 Patient 保存病人的编号、年龄和登记顺序。编号是字符串（比如 021033），所以用字符数组保存。

第三步，写比较函数，规则一层层比。 排序时自己写一个比较函数。先判断两人是不是老年人：一个老人一个年轻人，老人一定排前面；两个都是老人，先比年龄，年龄大的靠前，年龄相同再比登记顺序；两个都不是老人，直接按登记顺序排。

第四步，把登记顺序存进去并参与比较。 这里最关键的技巧是：把"登记顺序"也存进结构体并参与比较。这样所有先后关系都由比较函数决定，不会出现顺序乱掉的情况。sort() 本身不是稳定排序，但因为比较函数把登记顺序作为最后的比较依据，实际上完全确定了先后，谁先来谁就先看。以样例为例：两位老人 021033（75 岁）和 010158（67 岁）排最前面，75 岁更大所以 021033 先看；三位年轻人 021075、004003、102012 按登记顺序排在后面。最后每行输出一个病人编号即可。

**回顾总结。**排队问题三步走：先把规则分层，再写进比较函数，最后让 sort() 干活。最巧妙的一点是把"登记顺序"当成比较的最后一环，这样一来即使 sort() 不稳定，先后顺序也绝不会乱。

参考代码

// 病人排队：老年人优先，老年人按年龄降序（同年龄按登记顺序），非老年人按登记顺序
#include <iostream>
#include <algorithm>
using namespace std;

// 保存一名病人的信息
struct Patient {
    char id[15];   // 病人编号
    int age;       // 年龄
    int order;     // 登记顺序（1 开始）
};

// 自定义比较函数：先分老年人和非老年人，再按年龄和登记顺序比较
bool cmp(const Patient &a, const Patient &b) {
    bool isOldA = a.age >= 60;      // a 是否为老年人
    bool isOldB = b.age >= 60;      // b 是否为老年人
    if (isOldA != isOldB) return isOldA;              // 老年人排前面
    if (isOldA) {                                     // 两人都是老年人
        if (a.age != b.age) return a.age > b.age;     // 年龄大的靠前
        return a.order < b.order;                     // 年龄相同按登记顺序
    }
    return a.order < b.order;                         // 都不是老年人，按登记顺序
}

int main() {
    int n;
    Patient patients[105];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> patients[i].id >> patients[i].age;
        patients[i].order = i + 1;      // 记录登记顺序
    }
    sort(patients, patients + n, cmp);   // 按规则排序
    for (int i = 0; i < n; i++) {
        cout << patients[i].id << endl;
    }
    return 0;
}

复杂度分析

sort() 排序的时间复杂度是 O(n log n)，n 是病人个数（小于 100）。每个结构体保存一个编号字符串和两个整数，空间复杂度是 O(n)。n 很小，程序运行时间可以忽略不计。