見出し画像

ABC201 B 解答

mo

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 は整数

考察

二番目に高い山を求めます。

本問題は

２番に高い山の高さはいくつですか？

という問題でしたらとても簡単に求まります。山の高さをソートして２番目の数字を出力すれば答えです。

本問題はこれに少しだけ要素を加えます。今回はpairというものを用います。pair<int, int>のように使うことで、2つのものをセットとして使えます。

このpairをソートするとどうなるのでしょうか？

pairのソートは１つ目の値を基準にソートされます。もし、同じでしたら２つ目の値でソートされます。まさに出席番号と同じです。まずは名字（姓）の早い順で、同じ名字でしたら名前で判断されます。

スズキ　サブロウ
スズキ　ジロウ
タナカ　コウキ

こんな感じです。名前は適当です。これを「山の高さ」と「名前」の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をソートする問題の例題がありましたので紹介しておきます。


この記事が気に入ったらサポートをしてみませんか？