【題解】Luogu P1208 【[USACO1.3]混合牛奶 Mixing Milk】

(伪)面向对象

C++用类来解题

sort() + class + 贪心思想

设计一个类来保存每个奶农的信息(奶量和单价),然后定义compare函数用于比较,最后贪心求解即可。

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    class Farmer{

    public:

            int price;
            int milk;
    };
    bool compare(Farmer f1,Farmer f2){
        return f1.price < f2.price;
    }
    Farmer f[2000000];
    int main(){
        int n,m;//N是需要牛奶的总数;M是提供牛奶的农民个数。
        scanf("%d %d",&n,&m);
        for(int i = 0;i < m;i++){
            scanf("%d %d",&f[i].price,&f[i].milk);
        }
        sort(f,f + m,compare);//按单价从小到大排序
        int total = n;
        int min = 0;
        for(int i = 0;i < m;i++){
            if(total == 0) break;//当前需求量为0就退出
            if(total >= f[i].milk){//当前需求量大于奶农f[i]的奶量时,就全部买下来
                total -= f[i].milk;//当前需求量减去购买量
                min += (f[i].milk * f[i].price);//计算当前价格
            }else if(total < f[i].milk){//如果不够,能买多少买多少
                min += total * f[i].price;
                total = 0;
            }
        }
        printf("%d",min);
        return 0;
}