#問題概要
問題
$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)
.cpp
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;
}