[백준] 30022번: 행사 준비 - C++

https://www.acmicpc.net/problem/30022

 

$N$개의 물건을 적절하게 분배해서 가장 저렴하게 구매해야 한다. 예를 들어 두 상점이 각각 $1$, $5$원에 팔고 있다고 해보자. 1번 상점에서 사면 $4$만큼 이득을 볼 수 있다. 따라서 두 가격의 차이가 "잠재적인 이득"이 된다. 그리디하게 가장 큰 이득을 얻으려면 차이가 가장 큰 물건부터 우선적으로 구매해주면 된다. 따라서 차이가 큰 순서대로 정렬하고 최대한 저렴하게 구매하면 된다.

 

#include "bits/stdc++.h"

using namespace std;

struct Cmp {
    bool operator()(pair<int, int> &a, pair<int, int> &b) {
        int g1 = abs(a.first - a.second);
        int g2 = abs(b.first - b.second);

        return g1 > g2;
    }
};

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, a, b;
    cin >> n >> a >> b;
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i].first >> arr[i].second;
    sort(arr, arr + n, Cmp());

    long long ans = 0;
    for (auto p : arr) {
        if (a && b) {
            if (p.first < p.second) {
                a--;
                ans += p.first;
            } else {
                b--;
                ans += p.second;
            }
        } else if (a) {
            a--;
            ans += p.first;
        } else {
            b--;
            ans += p.second;
        }
    }

    cout << ans;
}