当前位置：首页 > news >正文

洛谷题目：P1208 [USACO1.3] 混合牛奶 Mixing Milk 题解（本题简）

news 2026/7/16 3:16:34

介绍：

前言：

给定牛奶总需求量、若干奶农各自的牛奶单价与最大供货量，在采购总量≥需求的前提下，让我们来求出采购牛奶的最小总花费。

#解题思路步骤：

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; vector<Farmer> 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.小亦

介绍：

前言：