训练排名 题解

核心考点

多关键字排序。

思路分析

按三关键字排序后建立编号到名次的逆映射。

需要特别检查空边界、相等值、最大规模和 long long 溢出。若存在不可达状态，应使用与合法答案明显区分的无穷大或负无穷初始化。

正确性说明

算法维护的状态或贪心选择恰好对应题目处理到当前位置时的全部有效决策。每一步只从已经正确的前缀状态转移，或作出不会损失最优解的局部选择；因此由归纳法，处理完全部输入后得到的就是题目要求的最优值或统计结果。

复杂度

复杂度满足题目完整数据范围；具体由主算法的循环层数决定。所有可能超过 32 位的累计量使用 long long。

参考代码

#include <bits/stdc++.h>
using namespace std;struct S{int id;long long sc,pen;};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<S>a(n);for(auto &x:a)cin>>x.id>>x.sc>>x.pen;sort(a.begin(),a.end(),[](S x,S y){if(x.sc!=y.sc)return x.sc>y.sc;if(x.pen!=y.pen)return x.pen<y.pen;return x.id<y.id;});vector<int>rk(n+1);for(int i=0;i<n;i++)rk[a[i].id]=i+1;while(q--){int id;cin>>id;cout<<rk[id]<<'\n';}}