[백준 4716] 풍선

문제

www.acmicpc.net/problem/4716

 

알고리즘

greedy

 

풀이

방 A, B에 풍선이 있고 각 팀마다 방마다의 거리와 얻을 풍선수가 주어질 때 최소로 이동하는 거리를 구하는 문제입니다.

 

이 문제의 답을 가장 방해(?)하는 것은 방과의 거리가 먼 팀입니다. 답을 최소로 만들어야하는데 먼 거리를 통해 해당 팀에 풍선을 전달하면 답을 찾기가 어려워집니다. 입력 예제에서 3번팀은 각 방과의 거리가 40과 10입니다. 거리가 10인 방을 이용해서 풍선을 전달해야 거리가 40인 방의 풍선을 전달받지 않아 최소로 답을 구할 수 있을 것입니다. 

 

그렇다면 우선적으로 고려해야할 것은 방과의 거리가 먼 팀일까요? 비슷하긴 하지만 답은 아닙니다. A방에서 가져올 풍선을 B방을 선택해서 이득을 보거나 B방에서 가져올 풍선을 A방을 선택해서 이득을 봐야합니다. 예를 들어 두 방과의 거리가 100, 100이라면 어느 방을 선택하건간에 가져올 수 있는 거리의 이득은 없습니다. 즉 두 방의 거리차가 클수록 먼저 고려해서 풍선을 이동시켜 해당 팀부터 풍선을 배부해야합니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef pair<int, int> pii;

int N, A, B;
int want[1000];
int distA[1000];
int distB[1000];
signed main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    while (1) {
        priority_queue<pii> pq;
        int ans = 0;
        cin >> N >> A >> B;
        if (N == 0 && A == 0 && B == 0)
            break;

        rep(i, N) {
            cin >> want[i] >> distA[i] >> distB[i];
            pq.emplace(abs(distA[i] - distB[i]), i);
        }
        while (!pq.empty()) {
            auto [gap, here] = pq.top();
            pq.pop();
            // cout << "here: " << here << '\n';
            int& getfrom = (distA[here] > distB[here] ? B : A);
            // cout << "getfrom: " << getfrom << '\n';
            if (getfrom) {
                int cnt = min(getfrom, want[here]);
                getfrom -= cnt;
                want[here] -= cnt;
                ans += cnt * min(distA[here], distB[here]);
            }
            ans += max(distA[here], distB[here]) * want[here];
        }
        cout << ans << '\n';
    }
    return 0;
}