Edited at

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;
}