AtCoder ABC 365 B - Second Best (6Q, 灰色, 200 点)

second best を求める系の問題

• 問題へのリンク

問題概要

個の相異なる整数 が与えられる。

この数列のうち 2 番目に大きいものについて、それが の何番目の要素であるかを求めよ。

制約

• 

解法 (1)：max と second max を管理する

1 つ目の方法として、最大値を求める方法を少し応用して、

• max：最大値
• second_max：2 番目に大きな値

を管理しながら、for 文を回す方法がある。次のコードのように書ける。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    int max = -1, max_index = -1, second_max = -1, second_max_index = -1;
    for (int i = 0; i < N; i++) {
        if (max < A[i]) {
            second_max = max;  // かつてのチャンピオンは 2 番目に後退
            second_max_index = max_index;
            max = A[i];
            max_index = i;
        } else if (second_max < A[i]) {
            second_max = A[i];
            second_max_index = i;
        }
    }
    cout << second_max_index + 1 << endl;
}

解法 (2)：ソートする

もう一つの解法は、数列 を大きい順にソートして、その 2 番目の要素を答える方法である。

ただし、「数列 の何番目か」を知る必要があるので、次の 個のペア値をソートすることにしよう。

---

---

これらを大きい順にソートして、2 番目の要素の second 要素を答えればよい。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<pair<int,int>> v(N);
    for (int i = 0; i < N; i++) v[i] = make_pair(A[i], i);
    sort(v.begin(), v.end(), greater<pair<int,int>>());
    cout << v[1].second+1 << endl;
}