【C++】pairのsecondを基準にソート（abc103_d）

提出

beta.atcoder.jp

抜粋

• pairの比較関数を定義すればいい

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main(){

    ...

    vector<pair<int, int> > pairs(M);

    // 入力
    FOR(i, 0, M){
        int a, b;
        cin >> a >> b;
        pairs[i] = make_pair(a, b);
    }

    // b順にソート
    sort(ALL(pairs), compare_by_b);

    ...
}

この問題の学び

• 左端a, 右端b のリストが与えられたとする
• 左端aでソートされた順に入力されているとする
• そのまま使うのではなく、右端bでソートし直す（図を書く）ことで解決策が浮かぶことがある

ノート (サンプル2を右端ソート・後端ソート)

C++ pair sortについて追記

• 結構アクセスがあるので追記

pairのfirstではなくsecondでソートしたい場合

• pairに入れる順番を逆にすればいい
  • 例：pair<int, string> としていたのなら、pair<string, int>とする

pairのfirstは昇順、secondは降順でソートしたい

どちらも数値の場合

• 降順でソート側は-1をかけて入れておけばいい
• 例

int a = 10;
int b = 20;
make_pair(a, -b);

firstが数字で降順、secondが文字列で昇順の場合

• 例：ランキング
  • 得点の高い順に表示（降順）
  • 同点なら名前のあいうえお順（昇順）
• 一番上の方に書いたように、比較関数を定義すればいい

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

// 比較関数
bool my_compare(pair<int, string> a, pair<int, string> b) {
    // 基本はfirstで比較
    if(a.first != b.first){
        // return a.first < b.first; // 昇順
        return a.first > b.first; // 降順
    }

    // それ以外はsecondで比較
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        // どちらも同じ
        return true;
    }
}

int main(){
    vector<pair<int, string> > V;

    V.push_back(make_pair(10, "takumi"));
    V.push_back(make_pair(100, "god"));
    V.push_back(make_pair(50, "g"));
    V.push_back(make_pair(10, "tenshin"));
    V.push_back(make_pair(0, "mr.z"));

    sort(V.begin(), V.end(), my_compare);

    for(int i=0; i<V.size(); i++){
        cout << V[i].first << ' ' << V[i].second << endl;
    }
}

出力結果

100 god
50 g
10 takumi
10 tenshin
0 mr.z