백준 4716번 풍선 - C++ 풀이

---

 

1. DA와 DB의 차가 큰 순으로 풍선을 배부한다.

 

1. DA와 DB의 차가 큰 순으로 풍선을 배부한다.

 A 풍선과 B 풍선의 합은 항상 K로 유지되어야 한다. 따라서 풍선이 모자라서 더 먼 곳을 택해야할 때 생기는 손해가 가장 큰 팀에게 먼저 풍선을 배부해서 손해를 줄여야 한다. 즉, | DA-DB | 값 내림차순으로 정렬한 뒤, 각 팀의 이동 거리가 최소가 되도록 배부해준다.

 

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Team {
    int k, da, db;  
};

int N, A, B;
vector<Team> teams;

bool cmp(const Team& lhs, const Team& rhs) {
    return abs(lhs.da - lhs.db) > abs(rhs.da - rhs.db);
}

void initTestcase() {
    teams.clear();
}

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

    while (true) {
        initTestcase();
        
        cin >> N >> A >> B;
        if (N == 0 && A == 0 && B == 0) break;
        
        for (int i=0; i<N; i++) {
            int k, da, db;
            cin >> k >> da >> db;
            teams.push_back({k, da, db});
        }
        
        // 반대를 골랐을 때 손해가 큰 순으로
        sort(teams.begin(), teams.end(), cmp);
        
        ll ans = 0;
        
        for (int i=0; i<N; i++) {
            int a, b;
            
            if (teams[i].da < teams[i].db) {
                a = min(A, teams[i].k);
                b = teams[i].k - a;
            }
            else {
                b = min(B, teams[i].k);
                a = teams[i].k - b;
            }
            
            ans += teams[i].da * a + teams[i].db * b;
            A -= a;
            B -= b;
        }
        
        cout << ans << "\n";
    }

    return 0;
}