AGC 012 A - AtCoder Group Contest
- 問題
- 解法
ぱっと見て、参加者を弱い順にソートしたとき最初の人をバラバラのチームに入れれば良いことが分かる。
チームの強さになる人のうち1番強い人は全体で2番目に強い人である。この人と全体で1番強い人と全体で1番弱い人を同じチームにすれば良い。
この3人を抜いた参加者で同じことを考える、ということを繰り返す。すると結局チームの強さの合計値の最大値は人を強い順に見て人目の強さの合計になる。
#include <iostream> #include <string> #include <algorithm> #include <cstdio> #include <vector> #include <queue> #include <set> #include <numeric> #include <cmath> using namespace std; typedef long long int ll; #define all(x) x.begin(),x.end() const ll mod = 1e9+7; const ll INF = 1e9; const ll MAXN = 1e9; int main() { ll n; cin >> n; ll m = 3*n; vector<ll> a(m); for(ll i = 0; i < m; i++){ cin >> a[i]; } sort(all(a)); reverse(all(a)); ll ans = 0; for(ll i = 1; i <= n; i++){ ans += a[i*2-1]; } cout << ans << endl; return 0; }