[Atcoder] ABC308 :: F - Vouchers

그리디로 풀 수 있는 문제이다.

N개의 아이템(P)이 주어지고, M개의 쿠폰 (L, D)가 주어진다. 이때 D <= L을 항상 만족하며, N개의 아이템에 M개의 쿠폰을 사용해서, 비용을 최소화해야 한다. 쿠폰을 사용하기 위해서는 L <= P을 만족해야 한다.

일단 가장 비싼 아이템 먼저 생각을 해보자. 그러면 떠올릴 수 있는 아이디어는 2가지인데,

1. D가 가장 큰 쿠폰을 사용한다. 2. L이 가장 큰 쿠폰을 사용한다. 이다. 하지만 이 두가지 접근법은 모두 정답을 보장할 수 없다는걸 어렵지 않게 파악할 수 있다.

그러면 가장 싼 아이템을 먼저 생각해볼 수 있고, 이때 P <= L인 모든 쿠폰 중 가장 D가 큰 쿠폰을 사용하면 최소의 비용을 보장할 수 있게 된다. 왜냐면 D <= L이라는 조건이 있기 때문이다. 만약 여기서 가장 할인율이 높은 쿠폰을 선택하지 않더라도, 이 쿠폰은 다음 아이템에 사용할 수 있게 되고 그러면 결국 할인되는 총 가격은 같은 값으로 수렴하게 된다. 따라서 매 순간마다 사용할 수 있는 쿠폰 중 D가 가장 큰 쿠폰을 선택하는 방법이 최선의 방법임을 보장하게 된다.

그래서 가장 싼 아이템부터 확인하면서 (L, D)를 PQ에 담고, 그때마다 가장 D가 큰 쿠폰을 사용하는 방식으로 구현하면 해결할 수 있다.

#include<iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int N, M;
vector<ll> v, l, d;
priority_queue<pll> pq;
priority_queue<ll> p;


int main()
{
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        ll x;
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    for (int i=0; i<M; i++) {
        ll x;
        cin >> x;
        l.push_back(x);
    }
    for (int i=0; i<M; i++) {
        ll x;
        cin >> x;
        d.push_back(x);
    }
    
    for (int i=0; i<M; i++) {
        ll x = l[i], y = d[i];
        pq.push({-x, y});
    }
    
    ll answer = 0;
    for (int i=0; i<N; i++) {
        ll num = v[i];
        while (!pq.empty()) {
            ll x = -pq.top().X, y = pq.top().Y;
            if (x > num) break;
            pq.pop();
            p.push(y);
        }
        
        if (p.empty()) {
            answer += num;
        } else {
            auto t = p.top();
            p.pop();
            answer += (num - t);
        }
    }
    cout << answer << '\n';
}