Good Pairs-Codeforces

投稿日：2022/03/31 更新日:2022/03/31

問題

整数列 $a_1, a_2, ...,a_n$ が与えられます。 $1 \leqq k \leqq n$ の $k$ に足して以下の等式を満たすペア $(i, j),1 \leqq i,j \leqq n$ を1つ見つけてください。

|a_i - a_k| + |a_k - a_j| = |a_i - a_j|

解法

数列中の最大値を $a_{\max}$ 、最小値を $a_{\min}$ とします。
$a_i = a_{\max}$ 、 $a_j = a_{\min}$ と条件を満たします。

\begin{aligned} |a_{\max} - a_k| + |a_k - a_{\min}| &= |a_{\max} - a_{\min}|\\ a_{\max} - a_k + a_k - a_{\min} &= a_{\max} - a_{\min}\\ a_{\max} - a_{\min} &= a_{\max} - a_{\min} \end{aligned}

実装

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

void solve(){
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i].first;
        a[i].second = i+1;
    }

    sort(a.begin(), a.end());
    cout << a[0].second << " " << a[n-1].second << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}