介绍题目传送门https://www.luogu.com.cn/problem/P1208前言给定牛奶总需求量、若干奶农各自的牛奶单价与最大供货量在采购总量≥需求的前提下让我们来求出采购牛奶的最小总花费。#解题思路步骤1、明确问题的规则与核心1.1、题目中给的每日牛奶的总需求量 n m个奶农 每个奶农呢有固定牛奶单价最大的时候可以供应奶量并且呢可以任意里采购不超过奶农上线整数牛奶求它们凑够 n 总量的最小采购总费用。1.2、从这道题捏其实不难看出这不就是经典的弹性问题嘛就是优先购买单价最便宜的牛奶并且保证总花费是最低的。1.3、这道题不考虑暴力枚举所有采购的组合时间复杂度高啊题中的规模那肯定是不行的啦。2、手把手采拆分步骤2.1、输入读入总需求 n 提供牛奶的农民个数为 m 并且循环 m 次读取每个奶农的一个单价和供应链并存入结构体的数组。2.2、进行排序我们将所有的奶农结构体按照 price 来进行从小到大的升序排列可以保证便宜货排在前面。2.3、进行遍历采购1️⃣如果剩余需求量的 remain 已经为 0 了那我们就直接跳出循环结束采购。2️⃣当前的奶农的全部产量剩下的需求全部买下总花费 单价的供应量剩余的来减去该奶农的所有产量。3️⃣当前奶农全部的产量 生育需求那我们只卖剩下需要的量总华为 单价剩余需求剩余的需求置于0。2.4、最后就是输出了我们直接打印总花费ok完成啦我俩真厉害##复杂度1、时间复杂度O(m log m)。2、空间复杂度O(m)。###代码#include iostream #include vector #include algorithm using namespace std; // 存储每个奶农的单价和供应量 struct Farmer { int price; int amount; }; // 排序比较函数单价升序优先买便宜的 bool cmp(const Farmer a, const Farmer b) { return a.price b.price; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int need, m; cin need m; vectorFarmer farmers(m); for (int i 0; i m; i) { cin farmers[i].price farmers[i].amount; } // 按单价从小到大排序 sort(farmers.begin(), farmers.end(), cmp); long long ans 0; int remain need; for (auto f : farmers) { if (remain 0) break; // 当前奶农全部能买下 if (f.amount remain) { ans 1LL * f.price * f.amount; remain - f.amount; } else { // 只买需要的部分 ans 1LL * f.price * remain; remain 0; } } cout ans endl; return 0; }--- 感谢观看---制作Code.小亦代码提供Code.小亦题目思路部分提供无代码部分思路提供无知识共享无知识查找来源无初审Code.小亦。终审Code.小亦。本文章属于原创作品禁止任何人进行转载除合作之外如在阅读中发现知识性错误、代码错误、错别字错误等情况私信博主或评论或通过邮箱2952104443qq.com。另题目来源首页 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)特本文章/专栏在知乎网站合规授权发布。