P76055 第 k 名有多少人 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76055，不要直接用于外站同名题。

解题思路

用 pair 保存两项成绩，按第一项降序、第二项升序排序，然后统计与第 k 名完全相等的成绩对数量。

复杂度

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

易错点

比较的是两项成绩都相同，不是仅第一项相同。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<pair<ll,ll>>a(n);
    for(auto &x:a)cin>>x.first>>x.second;
    sort(a.begin(),a.end(),[](auto x,auto y){if(x.first!=y.first)return x.first>y.first;return x.second<y.second;});
    cout<<count(a.begin(),a.end(),a[k-1])<<nl;
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。