练75.3 日期排序

解题思路

原串MM/DD/YYYY不能直接按字典序排序。分别取年、月、日构成比较键，按三项升序，同时保留原字符串输出。

正确性说明

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

易错点

原日期格式和前导零完整保留。

复杂度

时间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<string> a(n);
    for (auto &s : a)
        cin >> s;
    auto key = [](const string &s) {
        return make_tuple(stoi(s.substr(6)), stoi(s.substr(0, 2)), stoi(s.substr(3, 2)));
    };
    sort(a.begin(), a.end(),
         [&](const string &x, const string &y) { return key(x) < key(y); });
    for (auto &s : a)
        cout << s << "\n";
    return 0;
}