练76.1生日排序

解题思路

日期按年、月、日升序；相同日期按输入编号降序。结构体保存名字日期和原编号，再按这四关键字排序。

正确性说明

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

易错点

同生日要求后输入先输出，不能稳定保留原顺序。

复杂度

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

参考代码（C++11）

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

struct Student {
    string name;
    int y, m, d, id;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Student> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].name >> a[i].y >> a[i].m >> a[i].d;
        a[i].id = i;
    }
    sort(a.begin(), a.end(), [](const Student &x, const Student &y) {
        return make_tuple(x.y, x.m, x.d, -x.id) < make_tuple(y.y, y.m, y.d, -y.id);
    });
    for (auto &p : a)
        cout << p.name << "\n";
    return 0;
}