P4679 病人排队（入门）

解题思路

第一步，想想排队的规矩。 医院给病人排队，规矩是年龄大的病人优先看病，就像公交车上大家会主动让爷爷奶奶先坐一样。所以队伍要按年龄从大到小排：年龄最大的排最前面，年龄最小的排最后面。

第二步，把病人的两个信息“绑”在一起。 每个病人有两个信息：登记号和年龄。排队时这两个信息要成对一起移动，如果只单独排年龄，登记号就会对不上号。所以我们用结构体（struct）做一张“信息卡”，把登记号和年龄装在一起，移动时它们就始终手拉手。

第三步，让 sort 按年龄从大到小排。 C++ 的 sort 默认从小到大排，这里要反过来。我们写一个比较函数 cmp，告诉它：“如果第一个病人的年龄比第二个病人的年龄大，就认为第一个应该排在前面。” 就像老师规定“个子高的站前面”，小朋友就会自动按个子从高到矮排好。这样 sort 就能按年龄从大到小给病人排队了。

第四步，依次输出队伍。 排完队后，从第一个病人开始，一行一个，输出他的登记号和年龄，中间用空格隔开。比如有 5 个病人，年龄分别是 12、40、65、78、25，排完序后要按 78、65、40、25、12 的顺序输出对应的登记号和年龄。

第五步，想想边界情况。

• 如果只有 1 个病人（n=1），sort 几乎不用排序，直接输出这个病人就完成任务。
• 题目保证登记号和年龄都各不相同，所以比较时不会出现两个年龄相等“分不出胜负”的情况，比较函数很稳。
• n 小于 100，数组开到 105，多留一点空间，保证不会越界。

参考代码

// P4679 病人排队：按年龄从大到小给病人排队，依次输出登记号和年龄
#include <iostream>
#include <algorithm>
using namespace std;

struct Patient {
    int id;  // 登记号
    int age; // 年龄
};

// 比较函数：年龄大的病人排前面
bool cmp(const Patient &patient1, const Patient &patient2) {
    return patient1.age > patient2.age;
}

Patient patients[105]; // 存病人的登记号和年龄

int main() {
    int n; // 病人个数
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> patients[i].id >> patients[i].age; // 读入第 i 个病人的登记号和年龄
    }
    sort(patients, patients + n, cmp); // 按年龄从大到小排序
    for (int i = 0; i < n; i++) {
        cout << patients[i].id << ' ' << patients[i].age << endl; // 依次输出
    }
    return 0;
}

复杂度分析

sort 排序 n 个病人，时间复杂度 O(n log n)，n < 100，几百次操作，非常快。空间复杂度 O(n)，用来存病人的登记号和年龄。