けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 001 A - BBQ Easy (200 点)

伝説の始まり

問題へのリンク

問題概要

 2N 個の整数  L_1, L_2, \dots, L_{2N} が与えられる。これらを  2 個ずつ  N 組作り、各組についての「小さい方の値」の総和を最大にしたい。

制約

  •  1 \le N \le 100

考えたこと

小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまって損をする。

例えば、(3, 5, 98, 100) のとき、

  • (3 と 100)
  • (5 と 98)

みたいにしてしまうと、98 も 100 も消えて 3 + 5 = 8 となって大損である。このようなことを防ぐためには、小さいものは小さいもの同士、大きいものは大きいもの同士組んだ方がいい。

具体的には  2N 個の整数全体を小さい順にソートして ( R_1, R_2, \dots, R_{2N} とする)、その順に 2 つ組を作って行くのが良い。

念のための証明 (本番はここまでしなくて良さそう)

厳密に証明しようと思ったら、「その答えより小さくは絶対にできない」ことを言えば良くて、一般に

  •  k 番目の組のスコアが  R_{2k-1} より小さくはできない

ということが言えるので、全体として

  •  R_1 + R_3 + \dots

より小さくすることはできない。しかるにこれは「小さい順に 2 つ組を作る」という方法で達成できるので、これが最適解である。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> L(N*2);
    for (int i = 0; i < N*2; ++i) cin >> L[i];
    sort(L.begin(), L.end());
    int res = 0;
    for (int i = 0; i < N*2; i += 2) res += L[i];
    cout << res << endl;
}