ABC201 B 解答
B - Do you know the second highest mountain?(32)
問題
問題文
AtCoder国には N 個の山があり、i 個目の山の名前は Si, 高さは Ti です。
2 番目に高い山の名前を答えてください。N 個の山の名前、高さはそれぞれ相異なることが保証されます。
制約
2 ≤ N ≤ 1000
1 ≤ ( Si の長さ ) ≤ 15
1 ≤ Ti ≤ 10^5
Si ≠ Sj ( i ≠ j )
Ti ≠ Tj ( i ≠ j )
Si は英小文字、英大文字、数字のみからなる
N, Ti は整数
考察
二番目に高い山を求めます。
本問題は
2番に高い山の高さはいくつですか?
という問題でしたらとても簡単に求まります。山の高さをソートして2番目の数字を出力すれば答えです。
本問題はこれに少しだけ要素を加えます。今回はpairというものを用います。pair<int, int>のように使うことで、2つのものをセットとして使えます。
このpairをソートするとどうなるのでしょうか?
pairのソートは1つ目の値を基準にソートされます。もし、同じでしたら2つ目の値でソートされます。まさに出席番号と同じです。まずは名字(姓)の早い順で、同じ名字でしたら名前で判断されます。
スズキ サブロウ
スズキ ジロウ
タナカ コウキ
こんな感じです。名前は適当です。これを「山の高さ」と「名前」のpairで行えば本問題を解くことができます。
例)
3
Everest 8849
K2 8611
Kangchenjunga 8586
これをpair<int,string>に入れると次のようにソートされます(降順ソートです)。
8849 Everest
8611 K2
8586 Kangchenjunga
です。ここで、
1要素目に高さを入れる
高さはint型、名前はstring型で入れる
ことに注意しましょう。また、降順ソートをする際には
sort(V.rbegin(), V.rend());
のように「rbegin」「rend」とすればOKです。ソート後 [1] の要素のstring部分を出力しましょう。first,secondでアクセスできます。
実装
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int main()
{
int n;
cin >> n;
vector<pair<int, string>> v(n);
rep(i, n)
{
int t;
string s;
cin >> s >> t;
v[i] = make_pair(t,s);
}
sort(v.rbegin(), v.rend());
cout << v[1].second << endl;
return 0;
}
あとがき
降順ソートをしましたが、昇順ソートをして一番後ろから一つ前の要素を出力しても答えです。ただし、後ろのアクセスは少し面倒くさいので降順でソートした方が楽かなと思います。A問題でも書きましたが、速く正確にかける方法を考えるのがとても大切だと思います。時間がかかるだけでなく、WAを出してしまうとペナルティを貰ってしまいますからね。
pairをソートする問題の例題がありましたので紹介しておきます。
この記事が気に入ったらサポートをしてみませんか?