本文主要是介绍贪心之混合牛奶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*题目描述由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。
Marry乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。
给出Marry乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。
注：每天所有奶农的总产量大于Marry乳业的需求量。
输入输出格式
输入格式：
第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数；M,(0<= M<=5,000)是提供牛奶的农民个数。
第 2 到 M+1 行:每行二个整数:Pi 和 Ai。
Pi(0<= Pi<=1,000) 是农民 i 的牛奶的单价。
Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。
输出格式：
单独的一行包含单独的一个整数，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用。*/
AC代码：
#include<iostream>#include<algorithm>
#include"vector"
using namespace std;
typedef struct ex //典型借用vector容器对结构体进行快排，然后是简单的贪心
{
int price;
int num;
}ex;
int cmp(ex a, ex b)
{
return a.price < b.price; //sort排序方法函数：依据价格对容器内的结构体进行从小到大的排序！
}
int main()
{
int need, n, sum = 0, pay = 0;
cin >> need >> n;
int chazhi = need;
vector<ex> t(n);
for (int i = 0; i < n; i++)
{
cin >> t[i].price >> t[i].num;
}
sort(t.begin(), t.end(), cmp); //结构体是不能直接用快排对其结构体数组排序的，所以我们将多个结构体放入一个容器中
for (int i = 0; i < n; i++) //对这个容器用迭代器进行快排！
{
if (sum == need)
break;
else
{
if (t[i].num >= chazhi)
{
pay += chazhi*t[i].price;
sum += chazhi;
}
else
{
pay += t[i].num*t[i].price;
sum += t[i].num;
chazhi = need - sum;
}
}
}
cout << pay << endl;
system("pause");
return 0;
}
这篇关于贪心之混合牛奶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
