perogram

【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でソートし直す(図を書く)ことで解決策が浮かぶことがある

ノート

f:id:peroon:20181217050341j:plain

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