AtCoderログ：0068 - ABC 213 B

問題

問題文

$1,\ldots,N$ の番号のついた $N$ 人の選手がゲームを行いました。選手 $i$ のスコアは $A_i$ であり、スコアが小さい方が上位になります。
ブービー賞に該当する選手、すなわち、下位から $2$ 番目の選手の番号を求めてください。

制約

・$2 \le N \le 2 \times 10^5$
・$1 \le A_i \le 10^9$
・$A_i$ は相異なる
・入力に含まれる値は全て整数である

回答

回答1 (AC)

スコアをソートして下位から2番目の要素を取り出せば良いでしょう。設問のゲームではスコアが小さい方が上位になるので、昇順(小さい順)にソートした場合には、大きい方から2番目を取り出す必要があります。コードは以下のようになりました。

abc213b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  vector<int> a(n), b(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }
  copy( a.begin(), a.end(), b.begin() );
  sort( b.begin(), b.end() );
  
  for ( int i=0; i<n; i++ ) {
    if ( a.at(i)==b.at(n-2) ) {
      cout << i+1 << endl;
    }
  }
}

調べたこと

AtCoder の解説 → 公式解説

解き方は回答1と同じですが、実装には pair を使っていて、スコアと選手番号をペアとして保持することで、ソートした後の処理を簡略化していました。

学んだこと

• pair の第1成分に関するソートの処理方法

リンク

前後の記事

• 前の記事 → AtCoderログ：0067 - ABC 061 B