166A. Rank List

負数にする系（主語がでかい）
問題リンク

問題概要

チームの解答問題数、ペナルティ数が与えられる
上から番目にはいくつのチームが当てはまる可能性があるか

考えたこと

※以下出てくる用語はC++の用語として記載します

連想配列mapを用意する

• key: 解答問題数とペナルティのpair型
• value: keyをカウントするint型

降順にソート*1し，始めからチーム目に含まれるチームの総数が答え

keyの型がpairであるmapはpairのfirst優先のfirst, second昇順で格納されている

たとえば以下のようなpairの場合，

2 10
2 9
1 55

ソートすると以下の様になる

1 55
2 9
2 10

今回の問題では解決問題数が同じ場合，ペナルティが少ないほうが優位である
つまり，解決問題数は昇順，ペナルティ数は降順でソートする必要がある
これはペナルティ数に-1を掛け負数として扱う事でこれは解決する

コード

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    map<pair<int, int>, int> mp;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        mp[{a, -b}]++;
    }

    int cnt = n - k;
    for(auto x : mp){
        cnt -= x.second;
        if(cnt < 0){
            cout << x.second << endl;
            return 0;
        }
    }

    return 0;
}

*1:https://cpprefjp.github.io/reference/algorithm/sort.html