题目

题目描述

Merry Milk Makers 公司的业务是销售牛奶。它从农夫那里收购N单位的牛奶，然后销售出去。现在有M个农夫，每个农夫都存有一定量的牛奶，而且每个农夫都会有自己的定价。假设所有农夫的牛奶量总是可以满足MMM公司的进货量，现在我们需要做的就是计算出MMM最少需要花费多少钱来购买N单位的牛奶。

数据输入第一行给出两个整数N与M，接下来依次给出每个农夫牛奶的单价Pi与存有的牛奶的量Ai。

数据范围

1. 0 <= N <= 2000000
2. 0 <= M <= 5000
3. 0 <= Pi <= 1000
4. 0 <= Ai <= 2000000

样例输入

100 5

5 20

9 40

3 10

8 80

6 30

样例输出

630

解题思路

贪心算法，我们利用农夫牛奶的单价进行从小到大排序，然后我们按照这个顺序依次购买牛奶即可。

解题代码

/*

ID: yinzong2

PROG: milk

LANG: C++11

*/

#define MARK

#include<cstdio>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int MAXN = 5000+10;

int n,m;

struct Farmer {

    int price;

    int amount;

}f[MAXN];

bool cmp(Farmer a, Farmer b) {

    return a.price <= b.price;

}

int main() {

#ifdef MARK

    freopen("milk.in", "r", stdin);

    freopen("milk.out", "w", stdout);

#endif // MARK

    while(~scanf("%d%d", &n, &m)) {

        for(int i = 0; i < m; i++) {

            scanf("%d%d", &f[i].price, &f[i].amount);

        }

        sort(f, f+m, cmp);

        int sum = 0;

        for(int i = 0; i < m && n > 0; i++) {

            if(f[i].amount <= n) {

                n -= f[i].amount;

                sum += (f[i].amount * f[i].price);

            } else {

                sum += (n * f[i].price);

                n = 0;

                break;

            }

        }

        printf("%d\n", sum);

    }

    return 0;

}