贪心算法入门：打水问题中的最短作业优先与调度优化

小时候在公共水房打水最怕前面站着一个拎大铁桶的人。他一个人接水五分钟后面赶着上晚自习的学生全都得陪着等那时候大家默认先来后到就是天理。但我后来第一次认真接触“打水问题”时脑子里立刻闪过那个画面如果按接水时间从短到长排队所有人平均能少等一大截。这个看似简单的排队现象就是贪心算法最经典的入门场景之一。“打水问题”的标准表述是n个人排队接水第i个人需要t_i分钟只有一个水龙头问怎样安排顺序能让所有人等待时间的总和最小或者等价地让平均等待时间最小。它看着像脑筋急转弯其实是调度理论里“单机总完成时间最小化”问题的亲民版本操作系统里的短作业优先调度、服务器里的任务排队、车间里的工序排序都是同一个模型。这篇文章会从数学建模讲起把贪心策略为什么成立讲清楚再给可直接提交的代码最后聊几个高频变体和容易踩的坑。不管你是准备算法比赛、应付数据结构作业还是工作中要设计排队调度逻辑都值得花二十分钟把它彻底吃透。1. 打水问题的本质一场关于“等待”的数学优化1.1 把“排队接水”翻译成数学模型先把问题形式化。假设n个人最终排成的顺序是a_1, a_2, ..., a_na_i表示这个位置上的接水时间。按照常见的定义第i个人的等待时间W_i是“从开始排队到轮到他接水”的时长也就是他前面所有人的接水时间之和W_i a_1 a_2 ... a_{i-1}总等待时间就是所有W_i加起来。举个具体例子可能更有感觉四个人接水时间分别是[3, 2, 5, 1]。如果按这个原始顺序排队计算等待时间排队位置接水时间等待时间130223353254132510总等待时间 0 3 5 10 18平均每人4.5分钟。如果按接水时间升序排成[1, 2, 3, 5]排队位置接水时间等待时间11022133123451236总等待时间 0 1 3 6 10平均每人2.5分钟。同样四个人只是换了个排队顺序总等待从18分钟降到10分钟节省了将近一半。这就是顺序的力量。1.2 权重公式一眼看穿该把谁放前面总等待时间的展开式非常关键。设排序后的序列是a_1, a_2, ..., a_n那么W a_1 × (n-1) a_2 × (n-2) ... a_{n-1} × 1为什么因为排在第j位的人的接水时间a_j会被他后面的所有人各等待一次。第j位后面一共有n-j个人所以a_j对总等待时间的贡献就是a_j × (n-j)。最后一个位置后面没人贡献为0所以展开式只写到第n-1位。这个公式把动态的排队过程转化成了静态的加权和。每个位置有一个“放大系数”越靠前系数越大第一名的时间会被所有人重复等待放大n-1倍第二名被放大n-2倍以此类推。要让总和最小当然是把最小的接水时间放到放大系数最大的位置。这就是“短作业优先”的数学直觉来源它不是拍脑袋的公平问题而是加权和最小化问题。1.3 看清题目里的“等待时间”口径这里有个特别容易让人对不上答案的细节有些题目把“等待时间”定义为不包括自己接水时间的纯等待也就是前面所有人接水时间之和另一些题目则定义为“从到达一直到接完水离开”也就是W_i加上自己的接水时间a_i即完成时间C_i a_1 a_2 ... a_i。两种口径下总完成时间 总等待时间 所有接水时间之和。因为所有接水时间之和不随排序变化所以最优顺序完全一样都是升序但最终输出的数值会差一个固定常数。很多同学在洛谷、LeetCode上看到答案和自己算的不一样十有八九就是这个口径问题。做题前一定要先搞清楚它要你输出的是“纯等待总和”还是“完成时间总和”还是“平均等待时间”。2. 贪心策略推导最短接水时间为什么必须先来2.1 交换论证最优排列必须“从小到大”“把时间短的人放前面”这个结论太直观了直观到很多人懒得证明。但贪心算法的核心恰恰是证明这个局部最优选择为什么不会害了全局。最标准的证明是交换论证。假设存在一个最优排列其中某相邻位置k和k1分别站着接水时间为x和y的人并且x y也就是排在前面的反而时间长。现在考虑交换这两个相邻元素的位置。交换前后位置在k之前的人完全不受影响位置在k1之后的人也不受影响因为这两个人交换不会改变前面所有人接水时间之和。唯一变化的是这两个人之间的等待关系。设在第k位之前已经累计的前置等待时间为S。交换前第k位x的等待时间是S第k1位y的等待时间是Sx这两个位置的总等待时间是2Sx。交换后第k位y的等待时间是S第k1位x的等待时间是Sy总等待时间是2Sy。因为x y所以2Sy 2Sx交换后总等待时间严格减少。这说明“较大的数排在较小的数前面”不可能是最优的。于是最优排列中任意相邻位置都必须满足前一个不大于后一个也就是整体升序。这就是完整的证明简单、干净而且对任意n成立。2.2 贪心选择性质与最优子结构为什么可以一路选下去交换论证证明了最优排列是升序但这还不够还不够解释“贪心”为什么能嵌套。要证明贪心算法可行还得说明两件事贪心选择性质和最优子结构。贪心选择性质说的是每一步选的局部最优不会堵死全局最优的路。在打水问题里第一步的局部最优就是“让接水时间最短的人排第一”。如果某个最优排列的第一个位置不是最短时间t_min而是在某个位置p上那把t_min和第一个位置交换从权重公式看一个较小值从放大系数小的位置换到了放大系数最大的位置总等待时间只可能减少或不变。所以一定存在一个最优解以t_min开头。最优子结构也很自然把最短的人放到第一位后剩下的n-1个人面临的还是同一个“排队接水”问题只是人数少了一个目标仍然是让剩余的人总等待时间最小。于是同样的贪心选择继续执行一路选下去就构造出了全局最优解。这也是贪心和动态规划最本质的区别动态规划要枚举一堆状态再取最优贪心则是每一步直接做选择前提是证明当前选择不会排斥后续更优解。2.3 一个反直觉的疑问让大桶先打是不是更“公平”初学打水问题很多人会本能地反对“小桶先接”凭什么让接水时间短的人插队这不是欺负拎大桶的人吗从纯等待时间的角度看这个顾虑其实站不住脚。举个夸张的例子一个需要10分钟的大桶十个各需1分钟的小桶。如果大桶先打小桶们分别等待10、11、12……一直到19分钟总等待145分钟。如果小桶们先打前面十个小桶的总等待是012...945分钟大桶只等10分钟总等待55分钟。对比非常悬殊。背后的道理是让大桶排在前面大桶的10分钟会被后面每个人都等一遍放大十倍让小桶排前面虽然大桶要等十个小桶完成但小桶们彼此之间等得很少。少数人的不公平换来的是所有人总等待的大幅下降。在算法优化的语境里目标函数不是“每个人都不许吃亏”而是“总代价最小化”。当然真实世界的公平性还包含很多复杂维度但作为数学模型这个问题的答案非常明确短作业优先。3. 代码落地与边界陷阱从能跑到跑对3.1 两种等价的累加方式知道了排序策略代码本身很简单但累加等待时间有两种写法建议都掌握。第一种是前缀和模拟。遍历排序后的序列维护一个变量prefix表示当前已经累计在队伍前面的接水时间也就是下一人要等待的时间。每处理一个人先把当前prefix加入总等待再把他的接水时间累加到prefix里。这个过程和你手动算等待时间完全一致。第二种是直接用权重公式。排序后第i个数从0开始编号的接水时间会被后面n-1-i个人等待所以它直接贡献a[i] × (n-1-i)。这个写法代码更短但可读性稍差适合已经吃透公式之后使用。3.2 C与Python参考实现给出完整可提交的C代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); long long totalWait 0; long long prefix 0; for (int i 0; i n; i) { totalWait prefix; // 当前人的等待时间 前面所有人的接水时间之和 prefix a[i]; } // 输出总等待时间 cout totalWait \n; // 如果需要输出平均等待时间保留两位小数 // printf(%.2f\n, (double)totalWait / n); return 0; }Python版本n int(input()) times list(map(int, input().split())) times.sort() total_wait 0 prefix 0 for t in times: total_wait prefix prefix t print(total_wait) print(f{total_wait / n:.2f})如果题目要求输出排队方案比如有时候会输出每个人的序号就改用pair排序#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairlong long, int a(n); // 接水时间, 原始编号 for (int i 0; i n; i) { cin a[i].first; a[i].second i 1; } sort(a.begin(), a.end()); long long totalWait 0, prefix 0; for (int i 0; i n; i) { totalWait prefix; prefix a[i].first; } for (int i 0; i n; i) { cout a[i].second \n[i n - 1]; } cout fixed setprecision(2) (double)totalWait / n \n; return 0; }这里有一个小细节C的pair排序默认按first升序first相同再按second升序正好能保证接水时间相同的人按原始编号从小到大输出这在一些要求“多解时输出字典序最小方案”的题目里非常重要。3.3 最容易翻车的三个坑溢出、输出格式、方案顺序第一个坑是整数溢出。很多人只想到t_i本身不大却忽略了等待时间累加起来的量级。极端情况n100000每个t_i100000总等待时间大约是100000 × 99999 / 2 × 100000算出来接近5×10^14远远超过int能表示的2.1×10^9。所以C里必须用long long用int提交大概率WA或者输出负数。千万别觉得数据弱就没事这种题专门喜欢在边界数据上杀人。第二个坑是输出格式。有些题要求输出总等待时间有些要求平均等待时间保留两位小数还有些两个都要。如果你没看清题目直接把总等待输出上去很可能差之毫厘。C里保留两位小数建议用printf(%.2f)或者cout fixed setprecision(2)不要用setprecision不带fixed这样只会保留有效数字可能输出科学计数法。第三个坑是方案顺序。如果题目让你输出排队顺序记得把原始编号带上。排序的时候相同接水时间谁在前谁在后在求最小总等待时间时无所谓但在输出方案时就是完全不同的答案。稳定排序、pair的second排序、或者自定义比较函数时加上“时间相同按编号升序”的条件都是常见处理方式。还有多组测试数据的情况注意在每组循环里重置totalWait和prefix。4. 从打水问题出发变体、对比与贪心边界4.1 多水龙头先排序再找当前最闲的龙头单水龙头是最基础版本面试和竞赛里更常出现多水龙头变体n个人m个水龙头求最小总等待时间。这个问题的贪心策略分两步第一步还是把所有接水时间升序排列第二步用一个优先队列维护每个水龙头当前的累计接水时间每来一个人就把他安排到当前累计时间最小的水龙头上同时把他的等待时间累加进答案。为什么还要先排序因为每个水龙头内部本质上还是单队列队列内部依然满足短作业优先而跨队列的分配则要让每个水龙头的负载尽量均衡避免某个龙头闲死、某个龙头累死。优先队列选最小累计时间就是“谁最闲谁接新人”的贪心模拟。复杂度是O(n log n n log m)m很小的时候几乎可以当成O(n log n)。举个例子4个人接水时间[1, 2, 5, 6]2个水龙头。排序后按顺序分配1给龙头A累计12给龙头B累计25给A12A累计66给B26B累计8。等待时间分别是0、0、1、2总等待3。如果不懂贪心把6和1放同一个队列队列内等待就是0178另一个队列022总等待10。差距非常明显。4.2 带权重的打水问题谁着急谁先来现实中另一个合理变体是每个人的等待成本不一样。同是等一分钟赶飞机的人和悠闲的人承受的损失天差地别。于是引入权重w_i目标变成最小化sum(w_i × W_i)即加权总等待时间。这个版本的贪心规则会变。用交换论证推一下相邻两人i和j如果i在j前面那么j会比交换位置后多等t_i的时间额外代价是w_j × t_i反过来如果j在i前面i会多等t_j额外代价是w_i × t_j。要让i排在j前面更优就需要w_j × t_i ≤ w_i × t_j整理后得到t_i / w_i ≤ t_j / w_j。也就是说按t_i / w_i升序排列而不是简单按t_i升序也不是按t_i × w_i升序。这个规则叫加权最短作业优先WSJF在项目排期和任务调度里很常用。很多人第一次写这里会把排序键想反觉得“权重大的先来”就够了忽略了权重相同还要看时间。记住一个直觉这个比值衡量的是“每单位权重占用的时间”比值小的任务要么耗时短要么权重高理应优先处理。4.3 同样是贪心为什么“删数问题”不能排序热搜词里经常把“删数问题”和“打水问题”放在一起这俩都是贪心入门经典但策略完全不同。删数问题说的是给定一个n位正整数删去其中k位数字使剩下的数字保持原有相对顺序组成一个尽可能小的数。打水问题敢排序是因为“人的排列顺序”是决策变量我们完全自由。删数问题则完全不同数字的相对顺序是硬约束你不能把数字重新排列只能选择删谁留谁。如果贸然排序得到的数字根本不是原题要求的结果。它的贪心策略是从左到右扫描用一个栈维护当前保留的数字当遇到一个比栈顶更小的数字时说明栈顶这个“偏大的数字”应该被删掉直到删满k位扫描结束后如果还没删够就从末尾继续删。整体上是单调栈思路一趟遍历O(n)解决。对比项打水问题删数问题决策变量顺序可自由排列相对顺序不可变贪心核心排序短作业优先扫描单调栈维护证明方式相邻交换论证反证局部逆序必删复杂度O(n log n)O(n)这两个问题的对比可以给初学者一个很重要的认知贪心算法没有统一模板同一个关键词下的题目可能一个靠排序解决另一个靠单调栈解决。判断依据是“你能不能自由重排决策变量”。4.4 贪心失效的经典场景0/1背包反例最后必须泼一盆冷水贪心不是万能的。最经典的失效例子就是0/1背包问题。假设背包容量是10有三个物品A重量8价值9、B重量6价值6、C重量4价值4。按照单位重量价值贪心A的密度是9/81.125比B和C的1都高所以贪心会先选A选完剩余容量2什么都装不下总价值9。但最优解是选BC总价值10重量正好10。为什么打水问题贪心成立背包问题贪心失效关键区别在于打水问题里所有人都必须被接水只是一个排列问题不存在“选了谁就排斥了谁”的互斥关系而0/1背包里每个物品只有选或不选两种状态选择一个密度高的物品可能占满容量堵死了组合成更高价值的可能。容量是共享的稀缺资源局部最优很容易毁掉整体最优。所以看到一道贪心题至少先问自己三件事每一步贪的是什么东西选完这一步剩下的问题是不是和原问题同构如果多选了一个会不会把未来更优的组合方案堵死这三个问题过完再动手能少走很多弯路。最后再分享一个我长期用的小方法拿到贪心题别急着写代码先用十分钟把交换论证写一遍。打水问题就是检验这个能力的最佳标本能独立把交换论证讲明白你对贪心的理解就已经超过大多数人了。我之前带新人时总用这个题做基准效果比连刷十道模板题都管用。希望这顿“打水”对你也有帮助。