AtCoder ABC128 B - Guidebook(200点)

問題概要

問題

$N$個のレストランがある。レストランは$S$市に所属し、$P$点がついている。
$S$で辞書順に、辞書順で同じ場合は$P$の大きい順で並び替えて、レストランの番号を出力せよ。

制約条件

• $1≤N≤100$
• $S$ は英小文字のみからなる長さ
• $1$ 以上 $10$ 以下の文字列
• $0≤P_i≤100$
• $P_i$ は整数
• $P_i≠P_j (1≤i<j≤N)$

考えたこと

pair を作ってうまく並び替えたい。 first は降順で、 second は昇順で並び替える必要があるので単純に sort は不可能。

なのでまず sort をして辞書順にした後、 first で比較して同じだった場合 second を昇順に比較する sort をする。以下の記事を参考にして実装した。
【C++】pairのsecondを基準にソート（abc103_d）

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

これをもとの pair と比較してindexを取得して1を足せば答え。
時間計算量は$O(N^2)$。

解答

b.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<string, int> p;
bool compare_by_b(pair<string, int> a, pair<string, int> b) {
    if(a.first == b.first){
        return a.second > b.second;
    }else{
        return a.first < b.first;
    }
}

int main() {
    int n;cin >> n;
    vector<p> sp(n);
    vector<p> index(n);
    for(int i = 0; i < n; i ++) {
        string s; int p; cin >> s >> p;
        sp[i] = make_pair(s,p);
        index[i] = make_pair(s,p);
    }
    sort(sp.begin(), sp.end());
    sort(sp.begin(), sp.end(), compare_by_b);
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n; j ++) {
            if(sp[i].first == index[j].first && sp[i].second == index[j].second) cout << j+1 << endl;
        }
    }
    return 0;
}