Official
C - 最強ペアの結成 / Formation of the Strongest Pair Editorial
by
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:
