1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

AtCoder ABC128 B - Guidebook(200点)

Last updated at Posted at 2019-05-26

#問題概要
問題

$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;
}
1
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?