Problem 1.4.2 Mixing Milk

출처: https://train.usaco.org/usacogate

---

문제 설명

The Merry Milk Makers company buys milk from farmers, packages it into attractive 1- and 2-Unit bottles, and then sells that milk to grocery stores so we can each start our day with delicious cereal and milk.

Since milk packaging is such a difficult business in which to make money, it is important to keep the costs as low as possible. Help Merry Milk Makers purchase the farmers' milk in the cheapest possible manner. The MMM company has an extraordinarily talented marketing department and knows precisely how much milk they need each day to package for their customers.

The company has contracts with several farmers from whom they may purchase milk, and each farmer has a (potentially) different price at which they sell milk to the packing plant. Of course, a herd of cows can only produce so much milk each day, so the farmers already know how much milk they will have available.

Each day, Merry Milk Makers can purchase an integer number of units of milk from each farmer, a number that is always less than or equal to the farmer's limit (and might be the entire production from that farmer, none of the production, or any integer in between).

Given:

The Merry Milk Makers' daily requirement of milk
The cost per unit for milk from each farmer
The amount of milk available from each farmer
calculate the minimum amount of money that Merry Milk Makers must spend to meet their daily need for milk.
Note: The total milk produced per day by the farmers will always be sufficient to meet the demands of the Merry Milk Makers even if the prices are high.

입력 

Line 1: Two integers, N and M.
The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers wants per day.
The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from.
Lines 2 through M+1: The next M lines each contain two integers: Pi and Ai.
Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges.
Ai (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.

출력

A single line with a single integer that is the minimum cost that Merry Milk Makers must pay for one day's milk.

입력 예

100 5 
5 20 
9 40 
3 10 
8 80 
6 30

출력 예

630

---

문제 풀이

farmer unit price 를 기준으로 정렬해서, 가격이 낮은 순으로 최대한 사들이여서 필요한 양을 맞추도록 한다.

프로그램 내용

#define MAX_MILK 2000001
#define MAX_FARMER 5001

int main() {
    ifstream fin ("milk.in");
    ofstream fout ("milk.out");

    // Read requirement
    int amounts = 0, farmers = 0;
    fin >> amounts >>farmers ;

    vector <pair<int, int>> price_table;

    // reading price table
    for(int idx=0; idx < farmers; ++idx)
    {
		...    
	}

    // sorting unit_price
    sort(price_table.begin(),price_table.end()); 

    int purchased_amount =0, total_cost =0;
    for(int idx=0; idx < farmers; ++idx)
    {
        int current_amount=0;
        int need_amount = amounts - purchased_amount;
       
        if(need_amount > 0)
        {
            if( need_amount >= price_table[idx].second )
                current_amount = price_table[idx].second;
            else if (need_amount < price_table[idx].second)
                current_amount = need_amount;
        }

        purchased_amount += current_amount;
        total_cost += current_amount*price_table[idx].first;
    }

    fout << total_cost << endl;

 

Chapter 1. Getting started