USACO混合牛奶：贪心算法入门经典与代码实现详解

第一次在OJ上刷到“混合牛奶”这道题时我差点以为它是个模拟题——题目就白纸黑字放在面前每天要收购n单位牛奶m个农民每人给出自己的单价和最大供应量问最少花多少钱。直到我把样例手算了一遍、又写了几个随机数据拿去提交跑通之后才反应过来这道USACO 1.3里的混和牛奶 Mixing Milk其实是很多竞赛选手正式接触贪心算法时遇到的第一道“甜点”。它没有复杂的图论背景没有高深的DP状态设计甚至连数据范围都温和得不像话。但藏在这个简单故事底下的那个核心思路——“每次选当前单价最低的农户能买多少买多少”——会成为你之后处理无数贪心题目的地基。这篇文章我就用亲历者的视角把这道题拆开题目怎么读、代码怎么写、结论为什么成立、边界有哪些坑以及它真正值得你记住的思维方式。1. 题目背后的问题模型把“买牛奶”翻译成计算机能处理的数学语言1.1 原题到底在说什么需求、报价、供应量三者的关系先把题面老老实实还原一遍。你需要收购总量为n单位的牛奶市场上一共有m个农民可以供货。每个农民给出两个关键数字单价price_i以及他每天最多能卖给你的数量amount_i。也就是说同一单位牛奶的价格在不同农户手里可能是不同的而且每个农户的供货能力是有限的不是你想买多少就能买多少。你的任务是求出一个采购方案使得买够n单位牛奶的总花费最小。这里有几个容易被忽略的前提。第一牛奶是连续可分的资源——你可以向某个农民只买1.5单位也可以把他手里的货全部买走不存在“必须整箱买”这种限制。第二价格是给定的没有讨价还价的余地也不存在“买多了打折”之类的批发优惠。第三题目数据保证你一定能凑够数量换句话说所有农民的供应总量不小于n。把这个场景还原成数学模型其实就是一句话你有若干种商品每种商品有单位成本和库存上限现在要凑够指定数量求最小总成本。这是一个带容量上限的最小代价采购问题本质上跟“在预算有限的情况下从不同供应商采购元器件”“选择多个服务商凑够带宽”是同一个结构。1.2 为什么第一反应就应该是“按单价排序”而不是“算平均数”我第一次做这题的时候其实犹豫过一下要不要先算一个平均价再判断哪些农户“低于平均价”就多买点后来发现自己想复杂了。你先别管那些花哨的想法回归最朴素的直觉——你手里有一张购物清单要买固定数量的东西每个摊位价格不一样而且每个摊位存货有限。正常人会怎么做一定是从最便宜的摊位开始把便宜货尽可能多地扫进购物车直到清单上的数量被填满。这就是贪心策略的原型每一步都做当前看起来最优的选择且这个选择不会因为后续的操作而变差。你可能会问凭感觉是这么回事但它真的永远正确吗会不会存在一种情况因为前面买光了便宜货导致后面不得不买高价货整体反而更贵注意这里有一个容易被忽视的关键点牛奶的单价是固定的买得再多也不会让单价上涨。所以“便宜货买得越多”永远对总费用是好事不存在“买太多会触发涨价”的副作用。既然买低价牛奶永远不会带来负面后果那么从最便宜的开始买自然就是最优策略。1.3 这个模型里的“可分性”为什么这么重要在继续往下写代码之前我想先强调一个概念为什么混合牛奶适合贪心而很多其他题目不适合因为它满足“可分性”。你可以任意拆分子问题——从某个农户那里买多少都行买0.1单位也可以。这意味着每一步的局部最优选择都可以精确地“独立生效”。反过来如果题目改成“每个农户的牛奶必须整桶买每桶固定容量25单位”那问题就变味了。你可能因为某个便宜农户的剩余量是30单位全部买走会超出需求反而造成浪费于是需要权衡“买贵一点但刚好凑整”的方案。这就是经典的背包问题变体单纯按单价排序就不一定对了。所以看到一道题第一步不是急着套模板而是先判断资源是否可分。可分资源通常可以用贪心或者更简单的数学方法不可分资源往往需要往背包、动态规划那个方向想。这个判断能力比背会一道题重要得多。2. 贪心策略的实现与代码落地从结构体到排序的每一步2.1 读入与存储为什么用结构体而不是两个数组既然要按单价排序同时还要保留每个农民的供应量最简单的做法是把每个农民看成一个整体。两个平行数组当然也能写但排序的时候你会非常痛苦——排完price数组amount数组还得跟着动一不小心就错位了。所以我建议从一开始就用结构体struct Farmer { int price; // 每单位牛奶的单价 int amount; // 这个农民每天最多能供应多少 };然后用一个vector来装所有农民。这样排序的时候price和amount永远绑定在一起不会出现数据错位的低级错误。读入部分就更直接了先读需求总量n和农民个数m然后循环m次把每个农民的单价和供应量塞进vector。int n, m; cin n m; vectorFarmer farmers(m); for (int i 0; i m; i) { cin farmers[i].price farmers[i].amount; }这里有一个小细节值得说道说道我们并不需要记录农民的编号因为题目只问总花费不要求输出“从谁那里买了多少”。所以排序会打乱原来的输入顺序这完全无所谓。这个判断很重要——如果你将来做一道题它不仅要求最优解还要输出具体方案那你可能得在结构体里多存一个id字段或者用 pair 额外保存顺序。做题前想清楚“要不要保留原顺序”能省掉不少返工时间。2.2 排序用lambda还是手写比较函数按单价升序排列是整个贪心策略的核心动作。C里最简单的方式是用sort加一个自定义比较规则。你可以写一个单独的比较函数也可以直接用lambda表达式。我自己的习惯是在只有一处需要排序的题里直接写lambda因为代码更紧凑逻辑也更清楚sort(farmers.begin(), farmers.end(), [](const Farmer a, const Farmer b) { return a.price b.price; });如果你对lambda还不太熟也可以用传统写法bool cmp(const Farmer a, const Farmer b) { return a.price b.price; } sort(farmers.begin(), farmers.end(), cmp);两种写法效果完全一样。有一点需要特别提醒比较函数里千万不要写成return a.price b.price;也就是多加一个等号。原因在于sort要求比较规则满足“严格弱序”如果两个对象既“不大于”又“不小于”彼此它们就应该被视为等价。一旦你用了等号在某些编译器实现下会导致未定义行为有时候程序会崩有时候排序结果莫名其妙排查起来很费劲。这个错误我在早期写代码时踩过后来形成了条件反射——凡是写比较函数先检查有没有多余等号。可能有同学会问如果两个农民单价相同谁排前面有影响吗在这个题目里没有任何影响。因为单价相同意味着买谁的货花费都一样先买A后买B和先买B后买A算出来的总费用完全一致。所以不用纠结稳定排序的问题sort在这里是完全够用的。2.3 核心采购过程边买边扣两个分支要分清排序完成以后真正采购的逻辑其实只有几行。我们用一个变量表示“还差多少牛奶”初始等于n然后从头遍历排好序的农民。对于每个农民只有两种情况第一种情况他供应的量还不够填补剩余需求。这时候没得选只能全部买走。总花费加上“单价 × 他的供应量”剩余需求相应减少。第二种情况他的供应量已经足够填补剩余需求。那就只需要买“剩余需求”那么多总花费加上“单价 × 剩余需求”然后需求清零采购完成可以直接跳出循环。把这段逻辑翻译成代码long long totalCost 0; int remain n; for (const Farmer f : farmers) { if (remain 0) break; if (f.amount remain) { totalCost 1LL * f.price * f.amount; remain - f.amount; } else { totalCost 1LL * f.price * remain; remain 0; break; } } cout totalCost endl;这里有两个细节我要单独拎出来讲。第一个细节为什么写1LL * f.price * f.amount而不是直接f.price * f.amount因为price和amount都是int两个int相乘的结果会先被当成int处理如果乘积超出int上限就会溢出并得到错误结果。虽然这道题的数据范围比较友好但为了养成好习惯也为了应对变种题我建议大家凡是涉及乘法后再累加的场景都先把其中一个因子转成long long。这是一种成本极低的防御。第二个细节循环开头那个if (remain 0) break;是不是多余不完全是。如果你在第一种情况里已经买光了所有需求那么后面可能还有贷款农民但实际上循环已经不会再进入第二种情况的break了而是会继续检查后面的农民然后发现remain是0。加上这个判断一方面代码逻辑更清晰另一方面也覆盖了n初始为0的边界情况——如果需求本身就是0那么一进循环就跳出直接输出0非常干净。2.4 完整代码所有部分拼在一起的样子把前面几个片段合在一起就是一整道题的AC代码#include bits/stdc.h using namespace std; struct Farmer { int price; int amount; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorFarmer farmers(m); for (int i 0; i m; i) { cin farmers[i].price farmers[i].amount; } sort(farmers.begin(), farmers.end(), [](const Farmer a, const Farmer b) { return a.price b.price; }); long long totalCost 0; int remain n; for (const Farmer f : farmers) { if (remain 0) break; if (f.amount remain) { totalCost 1LL * f.price * f.amount; remain - f.amount; } else { totalCost 1LL * f.price * remain; remain 0; break; } } cout totalCost endl; return 0; }这段代码的时间复杂度是排序的 O(m log m)再加上一次 O(m) 的遍历。m 本身只有几千跑起来毫无压力。空间复杂度 O(m)用来存每个农民的信息。也许你会觉得这么短的代码有什么好讲的但真正让我觉得这道题有价值的恰恰是它在简短之外还藏着值得思考的东西为什么这个写法是对的如果哪一天数据变了这个写法还能不能继续用3. 正确性证明与边界处理为什么这题能被贪心“通吃”3.1 交换论证用一句反证法说服自己光靠“直觉上觉得对”不足以让人安心尤其是比赛里遇到贪心题你最好能快速验证思路是否有反例。对于混合牛奶有一个非常经典、也非常容易理解的证明方式叫交换论证。假设我们把农民按单价从低到高排好并按照这个顺序从前往后购买得到一个方案A。再假设存在某个最优方案B它不是按这个顺序买的。那么在方案B里一定存在两个农民一个单价更低的农民i没有买满同时另一个单价更高的农民j被购买了一些。为什么一定存在因为总需求是固定的如果低价的货没买够剩下的需求必然是由某个更贵的来源补上的。现在做一次“交换”从农民j那里少买一部分牛奶假设少买x单位转而从农民i那里多买x单位。单价上农民i更便宜所以这次交换后总费用只会下降不会上升。重复这个交换过程直到方案B变成“从最便宜的开始买满”的方案A。这个过程里总费用一直在下降或持平所以方案A的总费用不可能比最优方案B更差它本身就是最优的。这个证明最绝的地方在于它完全没用到什么高深数学工具思路就是“有便宜不占是浪费把贵的换成便宜的一定更好”。这种交换论证以后在贪心题里会反复出现比如活动安排、区间覆盖核心都是“如果当前方案和贪心方案不同就能通过交换改进”。建议你把这段话吃透因为很多新手以为贪心只是“猜一个策略然后交上去碰运气”其实它背后完全可以有严格的逻辑支撑。3.2 数据范围里的隐藏陷阱为什么答案要用long long题目给出的数据范围是多少简单回忆一下农民数量m通常不超过5000需求总量n可以到百万级别单价也可能到千级别。这意味着极端情况下总费用完全可能突破int的舒适区。我们不妨做一个简单的估算。假设n取一个比较大的值比如2,000,000单价取一个较大的值比如1000就算所有牛奶都来自一个高价农民总费用也是2,000,000 × 1000 2,000,000,000这个数字已经接近int的正上限2,147,483,647。如果单价数据再稍微宽一点或者总需求再大一点int就装不下了。更关键的是你在累加过程中可能不是一次加上全部而是分多次累加一旦中途的某个乘积或者累加结果越过边界程序就会得到完全错误的答案甚至出现负数。所以千万别省这个long long。在竞赛里“答案可能很大中间计算也可能很大”是最容易踩的坑之一养成“涉及金额、数量、长度一律开long long”的习惯能让你少流很多泪。这道题因为有原题数据兜底可能不开long long也能过但你想如果哪天遇到它的加强版或者你自己在别的地方复用了这段逻辑这个习惯就直接帮你避开了潜在风险。3.3 那几个容易忽略的边界场景n0、单价为0、供应刚刚好我自己平时做题有个习惯代码写完先不急着提交而是把几个特殊的边界情况在脑子里过一遍或者直接构造小数据跑一下。这道题有几个边界值得注意。第一个是需求量为0的情况。按照现实逻辑你一斤牛奶都不需要自然一分钱不花。代码会怎么走remain初始为0进入循环后第一件事就是if (remain 0) break;于是直接跳出去输出0完美。如果你忘了写这个break程序仍然会进入循环然后执行后面的判断虽然结果可能还是0但逻辑上绕了一道弯路而且如果遇到负数需求这种非法输入就会出问题。第二个是单价为0的情况。有些农民可能白送牛奶价格是0。这种情况下我们的代码会先把这些免费牛奶买走总费用不增加然后再去考虑付费的。这是完全正确的。有些人可能会担心总费用是0会不会有问题不会有问题输出0就可以了。第三个是某个农民的供应量恰好等于当前剩余需求。这种情况落在代码里会走进else分支买下剩余需要的部分remain变成0然后break。这里要特别注意别在边界处用“小于等于”还是“小于”的混淆。我经常看到有人写if (f.amount remain)然后两个分支都处理了一遍逻辑就乱了。我的习惯是“小于”表示供应不足必须全买“否则”表示足够只需要买剩下的这样两个分支的含义清清楚楚。4. 考场之外从这道题延伸出去的贪心思维与同类问题4.1 我在实际做题中踩过的三个小坑既然题目本身能AC那为什么还要单独聊踩坑因为我觉得做题的价值不只在“过”更在于从错误里提炼出通用的经验。这道题我前前后后给不少新同学讲过最常见的错误集中在三个地方。第一个坑是排序方向写反。有人想着“便宜优先”结果下意识把比较函数写成了return a.price b.price也就是按单价从高到低排序。这样程序也能跑样例也可能碰巧过但只要你构造一个“便宜货很多、贵货很贵”的用例立刻就能测出错误。我的建议是写完排序后先打印一遍排好的顺序肉眼确认是从小到大再往下写。第二个坑是忘记在循环里break。假设你已经买够需求了但后面还有一大堆农民如果不break程序会继续傻乎乎地判断“f.amount remain”而remain已经是0于是每个农民都会走第一种情况总费用被白白增加最后结果又大又错。这个错误特别隐蔽因为小数据可能看不出来只有当你构造一个“前面低价农民供应量总和大于需求”的数据时才会暴露。第三个坑是用int存单价乘以数量的中间结果。前面已经解释过这里就不再重复了。但我想强调这个坑不是“思路对不对”的问题而是“平台认不认”的问题很多时候你明明觉得逻辑没问题提交上去却是WA多半就是精度或溢出问题。4.2 一个不排序的做法基于价格桶的线性扫描按单价排序是这道题的标准解法但如果你观察一下数据范围会发现一个更有意思的视角单价的范围其实很小。既然单价有限那么我们可以不排序而是开一个桶下标就是单价桶里累加“该单价对应的总供应量”。具体来说读入每个农民时直接bucket[price] amount。然后从单价0开始往后扫描对于每个单价如果剩余需求还大于0就把这个价格对应的所有供应量拿出来填补需求。这样我们根本不需要对结构体排序也不需要关心农民之间的先后顺序因为同一个价格的所有牛奶是等价的合并在一起完全不影响答案。这个做法的复杂度是 O(m 价格范围)。在单价范围比较小的情况下它比排序更快而且代码也一样短。从这道题出发你可以记住一个泛化经验当排序关键字取值范围很小且是整数时桶排序是一个值得考虑的替代方案尤其是面对超大输入规模的场景。int n, m; cin n m; const int MAX_PRICE 1000; vectorint bucket(MAX_PRICE 1, 0); for (int i 0; i m; i) { int p, a; cin p a; bucket[p] a; } long long totalCost 0; int remain n; for (int price 0; price MAX_PRICE remain 0; price) { if (bucket[price] 0) continue; if (bucket[price] remain) { totalCost 1LL * price * bucket[price]; remain - bucket[price]; } else { totalCost 1LL * price * remain; remain 0; } } cout totalCost endl;你可能要问那这两种做法孰优孰劣其实在竞赛环境下sort版本的通用性更强因为你只需要改变比较函数就能适应各种排序规则而桶版本对数据范围的要求比较苛刻。但从学习角度我鼓励你把桶版本也写一遍它会帮你加深对“值域与排序”这层关系的理解。4.3 从“选最便宜”到“选最优性价比”模型迁移的边界在哪混合牛奶解决的是典型的“单位成本固定、资源可分”问题。顺着这个模型往前走你能遇到很多亲戚题比如多个供应商供货运费还不同比如多种原料混合每种原料成本不同甚至一些资源调度问题换成“从当前可选集合里拿成本最低的”。但是模型一旦发生变化贪心策略就要立刻跟着调整。举个例子如果题目改成“每种牛奶有一个固定品质分你在满足总需求量时必须让总品质分达到某个阈值”那就变成一个带约束的优化问题单纯按单价排序就不再成立因为你还得照顾品质要求。再有如果改成“每个农民有固定的起送费要么不买要么至少买一定数量”那么低价农户可能因为起送费反而变得不划算这时候最优策略可能要考虑“凑单”用贪心就不稳妥了。所以我把这道题看作一块试金石用来检验你对“贪心适用条件”的理解程度。每次碰到看起来像贪心的题脑子里应该自动过一遍三连问资源可分吗局部最优会不会影响后续有没有反例能推翻我的策略如果三个问题都通过了再动手写排序也不迟。写到这里想起一个同学问过的问题就这么一道入门题值得花这么久分析吗我的看法是恰恰因为它是入门题才值得把每一步为什么成立都想清楚。很多人在简单题上靠“感觉”AC了到难题上开始怀疑人生本质就是早期缺少对直觉背后的逻辑训练。混合牛奶这道题题目数据是温和的老朋友——但它教给你的那个思考框架才是真正能陪你走很远的东西。