これほとんど
と同じ問題！！！
問題概要
を整数として
個の整数
が与えられる。これらを 3 個ずつ
組のペアを作る。
ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを最大にせよ。
制約
考えたこと
AGC 001 - BBQ Easy の問題は、この問題で「3 つ組」ではなく「2 つ組」に関する問題だった。
それに比べると「3 つ組」になった分、少し難しくなる。パッと思いつく方法として、大きい順に並べて
12, 10, 9, 8, 6, 5, 4, 4, 2
として、これを順に 3 個ずつ区切って行く方法が思い浮かびそうになる。つまり
12, 10, 9 8, 6, 5 4, 4, 2
として 10 + 6 + 4 = 20 になる。しかしこれは嘘で、例えば一番目の「12, 10, 9」の 9 をこんなところで消費してはもったいない。真の最適解は、
12, 10, ? 9, 8, ? 6, 5 ?
のように、大きい方からとりあえず 2 個ずつ切って順にチームに入れて行って、残った下位 個をテキトーに入れていく方法になる。これが最適になることの証明は
で書いたものとまったく同じようにしてできる。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N; cin >> N; vector<long long> A(N*3); for (int i = 0; i < N*3; ++i) cin >> A[i]; sort(A.begin(), A.end(), greater<long long>()); long long res = 0; for (int i = 1, j = 0; j < N; i += 2, ++j) res += A[i]; cout << res << endl; }
