Mister雑記

競プロやります。

AGC001-A 「BBQ Easy」 (200)

コンテスト中に飯テロとは卑怯なり。

問題リンク

概要

 2N本の串があり、 i本目の長さは L_iである。

今からBBQをするために、以下のルールに従って串に具材を刺していく。

  • 串は2本1組で扱う。
  • 2本のうち短い方の長さを Lとしたとき、 L個の具材を刺すことができる。

具材は無限にあるものとする。このとき、串に刺すことができる具材の数の最大値を求めよ。

制約

  •  1 \leq N \leq 100
  •  1 \leq L_i \leq 100

解説

長い串と短い串をペアにしてしまうと、せっかくの長い串も上の条件からその長さを活かせなくなってしまい無駄が大きい。 そこで、短い串はできるだけ短い串とペアにして、この無駄を抑えるべきである。

まとめると、串を長さでソートして短い方から2本ずつ組にしていくのが最善策となる。

実装例

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

int main() {
    int N;
    cin >> N;

    int L[N * 2];
    for (int i = 0; i < N * 2; ++i) {
        cin >> L[i];
    }

    sort(L, L + N * 2);
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        // L[2i]とL[2i+1]を組み合わせる
        ans += L[i * 2];
    }

    cout << ans << endl;
    return 0;
}

感想

  • 昔のAGC-Aはここまで良心的な問題だったのか...。
  • ABCでも200点が妥当そう。