priority_queueのカスタム比較 【AtCoder Beginner Contest 137 D - Summer Vacation】

初投稿ですので、至らない所があればご指摘ください。

この問題はpriority_queueのカスタム比較をしなくても解けますが、自分は本番中にハマって、検索しても適当なものが出てこなかったので書いておきます。

priority_queueのテンプレート

priority_queue

namespace std {
  template <class T,
            class Container = std::vector<T>,
            class Compare = less<typename Container::value_type>>
  class priority_queue;
}

priority_queue - cpprefjp C++日本語リファレンス

通常の利用法

    priority_queue<int> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    // [ 3 2 1 ]

pushメソッドで追加された要素は降順に並ぶ。

並び順を昇順にしたいとき

    priority_queue<int,
                   vector<int>,
                   greater<int>> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    // [ 1 2 3 ]

Compareにgreater<int>を指定することで要素は昇順に並ぶ。

本題：並び順をカスタムしたいとき

並び順をカスタムしたいときはCompareを自作する。

class Compareとは何か

Compareは、比較演算関数オブジェクトを指定する。デフォルトの比較演算関数オブジェクトlessのテンプレートは以下のようになっている。

less

  // C++14
  template <class T = void>
  struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    using first_argument_type  = T;
    using second_argument_type = T;
    using result_type          = bool;
  };

less - cpprefjp C++日本語リファレンス
つまり、比較演算関数オブジェクトに必要なのは、**引数2つを取り、返り値がbool型であるoperator()**ということになる。

カスタム比較を使用してABC137Dを解く

D - Summer Vacation

2種類のpriority_queueを使用する。1つ目はpairの昇順、2つ目はpair.secondの降順->pair.firstの降順としている。

abc137d.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

struct comp2{
    bool operator()(const pair<int,int> &p1,const pair<int,int> &p2) const {
        if (p1.second == p2.second) {
            return p1.first < p2.first;
        } else {
            return p1.second < p2.second;
        }
    }
};

int main(void)
{
    int n,m;
    cin >> n >> m;
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq1;
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   comp2> pq2;
    
    for(int i = 0; i < n; i++) {
        int a,b;
        cin >> a >> b;
        pq1.push(make_pair(a,b));
    }

    int ans = 0;
    for(int i = 1;i <= m ; i++) {
        while(!pq1.empty() && pq1.top().first <= i) {
            pq2.push(pq1.top());
            pq1.pop();
        }
        if (!pq2.empty()) {
            ans += pq2.top().second;
            pq2.pop();
        }
    }

    cout << ans << endl;

    return 0;
}