BOJ 31760 Joys of Trading

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/31760
• 번역

문제

#

Apolyanka와 Büdelsdorf는 최근 접촉하게 된 두 개의 작은 신석기 시대 마을입니다. $1$부터 $N$까지 번호가 매겨진 $N$개의 자원이 있으며, 각 마을은 서로 다른 효율성을 가지고 이들 자원을 독립적으로 생산할 수 있습니다. 자원 $i$를 한 단위 생산하기 위해, Apolyanka는 $A_i$ 인시(person-hours)가 필요하고, Büdelsdorf는 $B_i$ 인시가 필요합니다. 현재 Apolyanka는 주어진 각 시간 기간에 자원 $i$를 $U_i$ 단위 생산하고 있으며, Büdelsdorf는 $W_i$ 단위를 생산하고 있습니다.

각 마을은 현재 최대 용량으로 작업하고 있습니다. 즉, 현재 사용하고 있는 것보다 더 많은 인시를 투입할 방법이 없습니다. 하지만 최근 발견된 무역의 이점을 통해, 두 마을 모두 필요한 모든 자원을 생산하면서도 총 작업 인시를 줄일 수 있으며, 따라서 절약된 인시를 휴식과 게임을 하는 데 사용할 수 있습니다. 필요한 것은 마을들이 협력하고, 작업을 조정하며, 자원을 교환하는 것뿐입니다.

예를 들어, $N = 2$이고, 자원 $1$은 나무, 자원 $2$는 식량이며, $A_1 = 1$, $U_1 = 2$, $B_1 = 4$, $W_1 = 1$, $A_2 = 2$, $U_2 = 1$, $B_2 = 3$, $W_2 = 4$라고 가정합시다. 그러면 Apolyanka는 $4$ 인시의 작업을 하고 있습니다: $U_1 = 2$ 단위의 나무를 생산하는 데 $A_1 \cdot U_1 = 2$, $U_2 = 1$ 단위의 식량을 생산하는 데 $A_2 \cdot U_2 = 2$입니다. 유사하게, Büdelsdorf는 $16$ 인시의 작업을 하고 있습니다: $W_1 = 1$ 단위의 나무를 생산하는 데 $B_1 \cdot W_1 = 4$, $W_2 = 4$ 단위의 식량을 생산하는 데 $B_2 \cdot W_2 = 12$입니다. 따라서 총 생산량은 $U_1 + W_1 = 3$ 단위의 나무와 $U_2 + W_2 = 5$ 단위의 식량이며, $4 + 16 = 20$ 인시가 필요합니다.

하지만 더 나은 조직이 가능합니다: Apolyanka가 $3$ 단위의 나무와 $0.5$ 단위의 식량을 생산하고, Büdelsdorf가 나무는 생산하지 않고 $4.5$ 단위의 식량을 생산할 수 있습니다. 각 자원의 총 생산량은 동일하지만, $3A_1+0.5A_2+0B_1+4.5B_2 = 3 + 1 + 13.5 = 17.5$ 인시만 필요합니다.

$N = 3$인 또 다른 예는 $A_1 = 1$, $B_1 = 2$, $A_2 = 2$, $B_2 = 1$, $A_3 = 1$, $B_3 = 1$이고, $i = 1, 2, 3$에 대해 $U_i = W_i = 1$입니다. 이 경우 각 마을은 현재 $4$ 인시를 작업하고 있습니다. 하지만 약간의 재조직을 통해 정확히 동일한 총 자원을 생산하면서 각각 $3$ 인시만 작업할 수 있습니다! 필요한 것은 Apolyanka가 자원 $2$를 한 단위 덜 생산하고 자원 $1$을 한 단위 더 생산하며, Büdelsdorf가 그 반대로 하는 것뿐입니다.

이러한 모든 값이 주어졌을 때, 정확히 동일한 총 자원을 생산하기 위해 마을들이 작업해야 하는 최소 총 인시는 얼마입니까? 자원 생산에 투자되는 인시는 정수일 필요가 없습니다.

입력

#

첫 번째 줄에는 자원의 개수를 나타내는 정수 $N$ ($1 \leq N \leq 10^5$)이 주어집니다. 각 자원은 $1$부터 $N$까지의 서로 다른 정수로 식별됩니다.

다음 $N$개의 줄 중 $i$번째 줄은 자원 $i$를 네 개의 정수 $A_i$, $U_i$, $B_i$, $W_i$ ($i = 1, 2, \dots, N$에 대해 $1 \leq A_i, U_i, B_i, W_i \leq 1000$)로 설명합니다.

출력

#

자원을 생산하는 데 필요한 최소 총 인시를 한 줄로 출력합니다. 출력은 최대 $10^{-9}$의 절대 오차 또는 상대 오차를 가져야 합니다.

🧐 관찰 및 접근

#

• 아니 이거 비교우위 내용 아님?
• 그럼 A국이나 B국이나 우위에있는놈이 일단 일을 다시키고.. 최대 일 양을 넘길 수 있으니 그쪽으로 보자
  • 같은경우는? 신경안써도 되는듯 누가해도 되니까
• 그담에? 그리디하게 비교우위인 비율대로 해서 뭐 이케저케 하면 될듯?
  • 아니 진짜 걍 되는데

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;
    ll A_budget = 0, B_budget = 0;
    vector<Resource> resources(N);
    rep(i, 0, N){
        ll A, U, B, W; cin >> A >> U >> B >> W;
        resources[i] = {A, B, (ld)U+(ld)W};
        A_budget += A * U;
        B_budget += B * W;
    }
    ld A_todo = 0, B_todo = 0;
    for(auto [A, B, amount]: resources){
        if(A < B) A_todo += A * amount;
        else if(B < A) B_todo += B * amount;
    }

    // A가 일을 풀로 하는 나라
    if(B_budget < B_todo){
        swap(A_budget, B_budget);
        for(auto &res: resources){
            swap(res.A_cost, res.B_cost);
        }
        swap(A_todo, B_todo);
    }

    sort(all(resources), [](const Resource &r1, const Resource &r2){
        return r1.B_cost * r2.A_cost > r2.B_cost * r1.A_cost;
    });

    ld ans = 0;
    ld A_used = 0, B_used = 0;
    for(auto [A, B, amount]: resources){
        if(A <= B){
            ld can_use = min((ld)amount * A, (ld)(A_budget - A_used));
            A_used += can_use;
            ans += (ld)can_use;
            amount -= (ld)can_use / A;
        }
        ld B_use = min((ld)amount * B, (ld)(B_budget - B_used));
        B_used += (ld)B_use;
        ans += (ld)B_use;
    }
    cout << fixed << setprecision(15) << ans << "\n";
}