csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：混合牛奶 Mixing Milk

csp信奥赛C高频考点专项训练之贪心算法 --【排序贪心】混合牛奶 Mixing Milk题目描述由于乳制品产业利润很低所以降低原材料牛奶价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。Marry 乳业从一些奶农手中采购牛奶并且每一位奶农为乳制品加工企业提供的价格可能相同。此外就像每头奶牛每天只能挤出固定数量的奶每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。给出 Marry 乳业每天对牛奶的需求量还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。注每天所有奶农的总产量不少于 Marry 乳业的需求量。输入格式第一行二个整数n , m n,mn,m表示需要牛奶的总量和提供牛奶的农民个数。接下来m mm行每行两个整数p i , a i p_i,a_ipi​,ai​表示第i ii个农民牛奶的单价和农民i ii一天最多能卖出的牛奶量。输出格式单独的一行包含单独的一个整数表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。输入输出样例 1输入 1100 5 5 20 9 40 3 10 8 80 6 30输出 1630说明/提示【数据范围】对于100 % 100\%100%的数据0 ≤ n , a i ≤ 2 × 10 6 0 \le n,a_i \le 2 \times 10^60≤n,ai​≤2×1060 ≤ m ≤ 5000 0\le m \le 50000≤m≤50000 ≤ p i ≤ 1000 0 \le p_i \le 10000≤pi​≤1000思路分析排序策略按单价升序排列农民确保优先购买价格最低的牛奶。贪心购买遍历排序后的农民列表尽可能多地购买低价牛奶直到满足需求。当无法完全购买当前农民的所有牛奶时购买剩余所需量并终止循环。复杂度排序的时间复杂度为O(m log m)遍历的时间复杂度为O(m)整体效率较高适用于题目给定的数据范围。代码实现#includebits/stdc.husingnamespacestd;constintN2e610;structnode{intp;// 单价ints;// 供应量}a[N];// 存储每个农民的信息boolcmp(node a,node b){returna.pb.p;// 按单价升序排序优先选择价格低的农民}intmain(){intn,m;cinnm;// 输入需要的牛奶总量和农民数量for(inti1;im;i){cina[i].pa[i].s;// 读取每个农民的单价和最大供应量}sort(a1,am1,cmp);// 将农民按单价从小到大排序intsum0;// 已购买的牛奶总量intans0;// 总花费for(inti1;im;i){if(suma[i].sn){// 如果当前农民的所有牛奶都可以购买suma[i].s;ansa[i].p*a[i].s;}else{// 否则购买剩余所需量ansa[i].p*(n-sum);break;// 已满足需求结束循环}}coutans;// 输出最小费用return0;}各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}