练76.2 精挑细选

解题思路

三个优先级依次为长度最大、直径最小、编号最大。用元组(length,-diameter,id)取最大，逐根比较更新即可，无需全部排序。

正确性说明

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

易错点

长度优先，不能为了更细牺牲长度。

复杂度

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

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    tuple<int, int, long long> best = {-1, 0, 0};
    for (int i = 0; i < n; i++) {
        int len, d;
        long long id;
        cin >> len >> d >> id;
        best = max(best, make_tuple(len, -d, id));
    }
    cout << get<2>(best) << "\n";
    return 0;
}