[BOJ][백준] 그리디 알고리즘-10590번: Burrito King

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

10590번: Burrito King

입력

The first line contains three integers n, A, and B (1 ≤ n ≤ 100 000, 0 ≤ A, B ≤ 10^9), the number of ingredients, the least amount of Albert’s joy and the maximal amount of Barney’s unhappiness. Each of the following n lines contains a description of an ingredient: three integers gi, ai, bi (0 ≤ gi, ai, bi ≤ 100) — the maximal number of grams allowed, the amount of Albert’s joy per gram and the amount of Barney’s unhappiness per gram.

출력

The first line of the output must contain two real numbers — the maximal amount of his joy and the amount of Barney’s unhappiness that Albert can obtain, satisfying the conditions in the problem statement, or “−1 −1”, if Albert cannot satisfy the conditions.

If the conditions are satisfiable the second line must contain n real numbers — the amount of each ingredient in grams.

Your output must have an absolute or relative error of at most 10^(-8).

Any way to reach maximal Albert’s joy that satisfies the given conditions can be printed.

 

---------------------------------------------------------------------------------------------------------------------

 

영어를 잘하는 편은 아니지만 해석을 해보자면, n명의 사람이 있고, 각 사람마다 a가중치, b가중치, g가중치가 주어집니다. 우리의 목표는, 각 사람마다 0부터 g가중치 까지의 임의의 소수를 부여하여 b가중치의 합을 B를 넘기지 않도록, a가중치의 합을 최대화 하는것이 목표입니다. 그리고  n번째 사람에게 gn만큼의 가중치를 부여했다면,  a가중치는 an*gn, b가중치는 bn*gn으로 더해지는 연산이 적용됩니다. 말이 너무 어려운가요? 예제를 봅시다.

 

2 5 5

2 2 1

2 2 4

 

다음과 같이 입력이 주어진다면, 우리는 첫번째 사람에게 (0~2)사이의 가중치 g1을 부여할것입니다. 그렇다면 a가중치는 2*g1, b가중치는 g1이 되겠네요, 마찬가지로 두번째 사람에게(0~2)사이의 가중치 g2를 부여한다면, a가중치는 2*g2, b가중치는 4*g2가 되어 a가중치의 합은 2g1+2g2, b가중치의 합은 g1+4g2가 됩니다. 따라서 문제를 간단히 줄인다면 

g1+4g2<=B 를 만족하는 2g1+2g2합의 최대화입니다. (0<=g1,g2<=2)

 

언뜻 생각하면 참 막막합니다.  n최대가 10만인데다 가중치가 소수로도 부여된다는 것이 이분탐색도 막막합니다.

하지만 b가중치의 합이 B를 넘기면 안된다는 점이 제약조건이고 이 것이 포인트입니다. a가중치를 최대화 하기 위해서는 gn이 커야함이 분명한데, b가중치의 합이 B를 넘기면 안된다는것은 곧 an이 bn보다 큰 사람부터 gn을 최대치로 부여하는것이 곧 최적해가 됨을 뜻합니다. an이bn보다 월등히 크다면 gn을 무조건 먼저 부여하는것이 최적해가 된다는 것이죠. 그리고 그 an이bn보다 큰지를 비교하기위해 an/bn순으로 정렬을 하고 우선순위가 큰 사람부터 최대 가중치를 부여하면 되겠습니다. 

 

위의 예제를 보자면, 첫번째사람의 an/bn은 2, 두번째 사람은 0.5가되므로 우선순위는 1번째사람-2번째사람이 됩니다. 1사람에게 gn의 최대치인 2를 부여하면 a가중치 합은 4,b가중치 합은 2가되고, 2번째사람에게는 b가중치의 합이 B가되도록 gn을 부여하는것이 곧 최적해가 됨을 뜻합니다. an이bn보다 월등히 크다면 gn을 무조건 먼저 부여하는것이 최적해가 된다는 것이죠. 그리고 그 an이bn보다 큰지를 비교하기위해 an/bn순으로 정렬을 하고 우선순위가 큰 사람부터 최대 가중치를 부여하면 되겠습니다. 

 

 

위의 예제를 보자면, 첫번째사람의 an/bn은 2, 두번째 사람은 0.5가되므로 우선순위는 1번째사람-2번째사람이 됩니다. 1사람에게 gn의 최대치인 2를 부여하면 a가중치 합은 4,b가중치 합은 2가되고, 2번째사람에게는 b가중치의 합이 B가되도록 gn을 부여하도록 (B-Bsum)/b[idx] 식을 사용하여 gn은 3/4=0.75를 부여하여 a가중치 합은(4+1.5), b가중치 합은(3+2)가 됩니다. 이제 코드로 옮겨볼까요?

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,A,B;
    cin>>n>>A>>B;
    vector<int>g(n),a(n),b(n);
    for(int i=0;i<n;i++)
    {
        cin>>g[i]>>a[i]>>b[i];
    }
    vector<pair<double,int>>v;
    for(int i=0;i<n;i++)v.push_back({(double)a[i]/b[i],i});
    sort(v.rbegin(),v.rend());

    vector<double>ans(n,0);
    double Asum=0,Bsum=0;
    for(int i=0;i<n;i++)
    {
        int idx=v[i].second;
        if((double)B>=Bsum+b[idx]*g[idx])
        {
            Bsum+=b[idx]*g[idx];
            Asum+=a[idx]*g[idx];
            ans[idx]=g[idx];
        }
        else
        {
            double tmp=(double)(B-Bsum)/b[idx];
            Bsum+=b[idx]*tmp;
            Asum+=a[idx]*tmp;
            ans[idx]=tmp;
            break;
        }
    }
    if(Asum<A)cout<<"-1 -1";
    else
    {
        cout<<fixed;
        cout.precision(8);
        cout<<Asum<<" "<<Bsum<<"\n";
        for(int i=0;i<n;i++)cout<<ans[i]<<" ";
    }

}

]시간복잡도는 정렬에 NlogN이 소요되는것 외에는 g가중치를 부여하는 N의시간밖에 없으므로 O(NlogN)이 자명합니다.

마지막 부분에 Asum이 A를 넘지 않으면 -1 -1을 출력하는 것과, 부동소수점을 표현하는 cout<<fixed 와 precision(8)로 소수출력을 한 부분에 유의해주시면 됩니다.