Official

C - 最強ペアの結成 / Formation of the Strongest Pair Editorial by physics0523


最強ペアとはどのようなものでしょうか?
単にプログラミング能力の大きい方から \(2\) 人を選択すれば、総合力が最大となります。

なので、 \(A\) を降順ソートして先頭 \(2\) つの値の和を答えることでこの問題に正答できます。

時間計算量は \(O(N \log N)\) 、空間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  sort(a.rbegin(),a.rend());
  cout << a[0]+a[1] << "\n";
  return 0;
}

大きい方から \(2\) つの値のみを維持することで、時間計算量 \(O(N)\) 、空間計算量 \(O(1)\) で解くこともできます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  int p=0,q=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    if(a>p){q=p; p=a;}
    else if(a>q){q=a;}
  }
  cout << p+q << "\n";
  return 0;
}

posted:
last update: