微网站设计制作,wordpress支付宝会员,中建八局一公司总部在哪,商丘免费网站建设开发公司[USACO1.3] 混合牛奶 Mixing Milk
题目描述
由于乳制品产业利润很低#xff0c;所以降低原材料#xff08;牛奶#xff09;价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。
Marry 乳业从一些奶农手中采购牛奶#xff0c;并且每一位奶农为乳制品加工企业提…[USACO1.3] 混合牛奶 Mixing Milk
题目描述
由于乳制品产业利润很低所以降低原材料牛奶价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。
Marry 乳业从一些奶农手中采购牛奶并且每一位奶农为乳制品加工企业提供的价格可能相同。此外就像每头奶牛每天只能挤出固定数量的奶每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。
给出 Marry 乳业每天对牛奶的需求量还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。
注每天所有奶农的总产量大于 Marry 乳业的需求量。
输入格式
第一行二个整数 n , m n,m n,m表示需要牛奶的总量和提供牛奶的农民个数。
接下来 m m m 行每行两个整数 p i , a i p_i,a_i pi,ai表示第 i i i 个农民牛奶的单价和农民 i i i 一天最多能卖出的牛奶量。
输出格式
单独的一行包含单独的一个整数表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。
样例 #1
样例输入 #1
100 5
5 20
9 40
3 10
8 80
6 30样例输出 #1
630提示
【数据范围】 对于 100 % 100\% 100% 的数据 0 ≤ n , a i ≤ 2 × 1 0 6 0 \le n,a_i \le 2 \times 10^6 0≤n,ai≤2×106 0 ≤ m ≤ 5000 0\le m \le 5000 0≤m≤5000 0 ≤ p i ≤ 1000 0 \le p_i \le 1000 0≤pi≤1000
题目翻译来自 NOCOW。
USACO Training Section 1.3 思路
贪心思想优先选最便宜的即为最优选择
首先定义一个结构体Snode其中包含两个成员变量p和a分别用于存储每位奶农提供的牛奶的单价和他们每天能提供的最大牛奶量。然后定义了一个自定义排序函数cmp这个函数在后续的排序操作中按照牛奶的单价进行升序排序如果单价相同则按照每日最大产量进行降序排序。
在主函数中首先输入需要的牛奶总量n和提供牛奶的农民数量m。然后对于每位农民输入他们的牛奶单价和每日最大产量并将其保存在一个Snode类型的向量v1中。接着对v1进行排序这样后续就能按照牛奶的单价从低到高进行采购。
在采购过程中从单价最低的农民开始如果他们的最大产量大于当前的需求量那么就只购买需要的数量并将花费加到总花费中然后结束采购过程。否则购买他们的全部产量然后从下一个单价的农民那里继续购买直到满足全部需求。最后输出总的采购成本。 AC代码
#include algorithm
#include iostream
#include vector
#define ll long long
#define AUTHOR HEX9CF
using namespace std;struct Snode {int p, a;
};bool cmp(Snode x, Snode y) {if (x.p y.p) {return x.a y.a;}return x.p y.p;
}vectorSnode v1;int main() {int n, m;cin n m;for (int i 1; i m; i) {Snode t;cin t.p t.a;v1.push_back(t);}sort(v1.begin(), v1.end(), cmp);auto it1 v1.begin();ll ans 0;while (n) {if (n it1-a) {ans it1-p * n;break;}n - it1-a;ans it1-p * it1-a;it1;}cout ans endl;return 0;
}
