【例76.1】 病人排队

解题思路

使用stable_sort。老年与非老年混合时老年优先；都老年时年龄大优先；都非老年视作相等保持登记顺序，老年同龄也保持顺序。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

60岁属于老年；不能把年轻人按年龄排序。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<string, int>> a(n);
    for (auto &p : a)
        cin >> p.first >> p.second;
    stable_sort(a.begin(), a.end(),
                [](const pair<string, int> &x, const pair<string, int> &y) {
                    bool p = x.second >= 60, q = y.second >= 60;
                    if (p != q)
                        return p;
                    if (p)
                        return x.second > y.second;
                    return false;
                });
    for (auto &p : a)
        cout << p.first << "\n";
    return 0;
}