打水问题这道题我在蓝桥杯备赛群里见过太多次了几乎每年都有同学栽在“为什么排序后还要动态分配水龙头”这个点上。实际上它就是一个披着生活场景外衣的贪心算法题核心模型和工作站调度、任务排队是一模一样的。这篇文章我会把题目拆透从贪心证明到代码实现再到多水龙头的隐藏细节一次性说清楚。先给没做过这道题的朋友交代一下背景。蓝桥杯算法提高VIP级别的“打水问题”题目编号1523描述非常生活化有n个人到r个水龙头打水每个人装满水桶的时间不同问怎么安排顺序能让大家的等待时间总和最小。输入第一行是n和r第二行是n个人的打水时间输出是安排后的最少总等待时间。数据规模不大但考察的贪心思想非常典型理解了它以后遇到“排队优化”“资源分配”类题目都会轻松很多。1. 题目理解与贪心思路1.1 先把问题翻译成算法语言这种生活化题目第一步永远是抽取数学模型。n个人是n个任务每个人有个固定耗时t[i]r个水龙头就是r台可以并行处理任务的机器每个人从到达队列开始到轮到自己打水完毕中间所有等待时间累加起来就是我们要最小化的目标。有个关键点容易混淆题目问的“总等待时间”一般只统计每个人在轮到自己之前干等的时间不包括自己实际打水的那段时间。比如你等了5分钟打水用了3分钟你的“等待时间”是5分钟不是8分钟。你如果理解成“从开始到结束的全部时间”那贪心结论虽然不变但计算量会差很多后面讲代码的时候会再次强调。这个模型的本质是有r个并行服务台n个任务待调度每个任务的加工时间已知且不可分割目标是最小化所有任务的等待时间之和。这在运筹学里叫“单阶段并行机调度问题”经典结论就是最短处理时间优先也就是SPT规则。1.2 为什么短任务应该排在前面很多人第一反应是“让打水快的人先来那慢的人不是等更久吗”乍一听好像该让慢的人先打其实完全反了。这里的核心是减少“被拖累”的人数而不是照顾某一个人。举个最简单的例子只有一个水龙头两个人一个洗水桶要1分钟一个要10分钟。如果让10分钟的人先来后面那个人干等10分钟总等待时间10分钟如果让1分钟的人先来后面那个人只等1分钟总等待时间是1分钟。差了整整9分钟。为什么会差这么多因为排在前面的人他的打水时间会被后面所有人都“继承”一次。10分钟先生来10分钟的等待成本被传递给了后面每一个排队者1分钟先生来那1分钟就被乘以了后面的人数。所以整体最优就是处理时间短的尽量往前放这和“操作系统里的短作业优先调度算法”是一个原理。1.3 用交换论证证明贪心正确性写题解的人经常直接说“排序后计算”但比赛时候如果对证明没把握改一个问法就容易懵。这里我给出一个特别直观的交换论证理解了以后终身难忘。假设当前队列中有两个人A的打水时间是aB的打水时间是b且a b他们前面已经排了k个人这k个人的总等待时间用S表示后面还有若干人用M表示。如果顺序是A在前B在后A的等待时间SB的等待时间S a后面所有人每人平白多等a b总共多等M × (a b)总等待时间 S (S a) M × (a b)如果交换成B在前A在后B的等待时间SA的等待时间S b后面所有人每人平白多等a b总共还是M × (a b)总等待时间 S (S b) M × (a b)比较两种情况差值只在中间那两项a和b。因为a b所以B在前A在后更优。也就是说任意相邻两个任务只要前者耗时大于后者交换之后总等待时间一定不增加。一路交换下去最后必然得到一个耗时从小到大的序列这就是贪心策略的正确性来源。注意这套证明里“后面所有人”的总等待时间没有变化因为两段任务总的占用时间相同所以关键就落在被交换的两个人互相等待的成本上。这个思想可以延伸到很多题目以后遇到“排队接水”“仓库搬货”之类的问题都可以直接套。2. 多水龙头场景下的分配策略2.1 单一队列还是动态分配加了“r个水龙头”这个条件后问题就变得有意思了。有些同学会以为反正r个水龙头是并联的那直接把所有人按时间排序然后一个一个按顺序塞给水龙头就行其实没那么简单。如果你按排序后的顺序前r个人分别去r个水龙头第r1个人该去哪个直觉是去当前累计时间最少的水龙头这个策略叫“最短当前负载优先”。为什么不是永远去1号水龙头因为这样1号水龙头的队伍会越排越长其他水龙头空着显然不是最优。标准做法是先把所有人按打水时间从短到长排序然后逐个安排。安排第i个人时看当前r个水龙头各自已经累计了多少打水时间选累计时间最少的那一个把这个人安排过去同时让他的等待时间等于该水龙头当前的累计时间再更新这个水龙头的累计时间。这里有个特别漂亮的等价写法因为序列已经升序所以第1个人去1号水龙头第2个人去2号水龙头……第r个人去r号水龙头第r1个人回1号水龙头第r2个人回2号水龙头以此类推。也就是第i个人去编号为(i - 1) % r 1的水龙头。这是排序后“最小负载优先”策略的自然结果因为每次肯定是最早空闲的水龙头被选走。2.2 为什么累计时间最小意味着等待时间最小这里再往深挖一层。当第i个人到来时他面对的r个水龙头各自有一些累计打水时间他加入某个水龙头后等待时间就是那个水龙头当前的累计时间。比如1号水龙头前面已经有两个人累计干了5分钟那第三个人来这儿就要等5分钟。为了让这个新来的人等待时间最小当然应该选累计时间最少的水龙头。那这个局部最优会不会影响别人不会。因为每个人只会被安排一次一旦安排完他的等待时间就固定了后续新来的人选择水龙头时也只关心当前的累计时间。每一步都选当前累计时间最少的恰好就是全局最优的贪心策略。为了直观我平时会让学员先手动模拟一组数据。比如n5、r2打水时间分别是3、2、5、4、1。排序后是1、2、3、4、5。前两个人分别去1号、2号水龙头等待时间都是0第三个人时间3此时1号水龙头累计12号累计2选1号等待时间11号累计变成4第四个人时间4此时1号累计42号累计2选2号等待时间22号累计变成6第五个人时间5此时1号累计42号累计6选1号等待时间41号累计变成9。总等待时间001247。我见过很多第一次学这个模型的同学卡在“为什么第4个人不去1号而是去2号”因为3号刚把1号水龙头的累计从1变成了42号只有2虽然2号的原始编号排在后面但它的负载更小。这就是动态分配和机械按编号轮换的本质区别手动模拟一遍就懂了。2.3 单水龙头是多水龙头的特例如果r1多水龙头模型自动退化成单队列。此时所有人排成一队第i个人的等待时间是前i-1个人打水时间之和。总等待时间等于对排序后的时间序列做前缀和再把除第一个人以外的前缀和全部加起来。为什么第一个人的前缀和不加因为第一个人等待时间是0。这一点在写代码时特别容易踩坑。如果直接写“ans 前缀和”会把第一个人的0加上去虽然不影响结果但边界上容易把循环范围搞错。更稳妥的做法是从第二个位置开始累加或者先给第一个位置赋值0。我以前带集训队的时候有个学员用前缀和写法循环从1到n全加了一遍提交上去答案多了一截。排查了半天发现就是第一个人的等待时间不该算进来。这种边界问题在蓝桥杯这种OJ上能卡掉一大片人因为你本机测试数据小看不出错一交上去就WA。2.4 代码实现与关键步骤详解3.1 C完整代码看代码之前先确定输入输出格式。题目第一行输入n和r第二行输入n个正整数表示每个人的打水时间。输出是一个整数表示最小的总等待时间。这里题目给的时间不一定有序所以第一步永远是排序#include bits/stdc.h using namespace std; int main() { int n, r; cin n r; vectorint t(n); for (int i 0; i n; i) { cin t[i]; } sort(t.begin(), t.end()); // 短任务优先 vectorint sum(r, 0); // 每个水龙头当前的累计打水时间 long long ans 0; // 总等待时间用 long long for (int i 0; i n; i) { // 找到当前累计时间最少的水龙头编号 int idx 0; for (int j 1; j r; j) { if (sum[j] sum[idx]) { idx j; } } ans sum[idx]; // 这个人要等 sum[idx] sum[idx] t[i]; // 该水龙头累计时间增加 } cout ans endl; return 0; }这段代码的时间复杂度是O(n log n n × r)因为排序是O(n log n)后面每安排一个人都要扫描一遍r个水龙头所以还有O(n × r)。数据规模小的时候完全没问题但如果r也很大比如n和r都是10^5量级就需要优化了。优化也不难用一个优先队列小根堆来维护每个水龙头的累计时间。每次弹出最小的累计时间加上当前任务的耗时再塞回堆里。时间复杂度从O(n × r)降到O(n log r)代码还更简洁#include bits/stdc.h using namespace std; int main() { int n, r; cin n r; vectorint t(n); for (int i 0; i n; i) cin t[i]; sort(t.begin(), t.end()); priority_queueint, vectorint, greaterint pq; for (int i 0; i r; i) pq.push(0); // 初始累计时间都是0 long long ans 0; for (int i 0; i n; i) { int cur pq.top(); pq.pop(); ans cur; // 当前人的等待时间 pq.push(cur t[i]); // 更新水龙头累计时间 } cout ans endl; return 0; }优先队列版本是很多高级题解的标准写法因为逻辑更清晰而且天然体现了“每次选当前最优”的贪心栈。我强烈建议你把两种都会写比赛时如果时间紧张直接写第一个版本求稳如果想展示更好的复杂度或者应对加强版数据就写堆优化版本。3.2 Java版本与Python版本要点蓝桥杯有C/C、Java、Python等多个组别这里我把Java和Python的核心区别点一下。Java版本基本是C的翻版唯一需要注意的是比较器和容器类型。用int数组排序然后维护一个int数组记录水龙头累计时间每次找最小。用PriorityQueue的时候记得传Comparator.reverseOrder的反转否则默认是小根堆刚好符合需求import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int r sc.nextInt(); int[] t new int[n]; for (int i 0; i n; i) t[i] sc.nextInt(); Arrays.sort(t); PriorityQueueInteger pq new PriorityQueue(); for (int i 0; i r; i) pq.offer(0); long ans 0; for (int i 0; i n; i) { int cur pq.poll(); ans cur; pq.offer(cur t[i]); } System.out.println(ans); } }Python版本这里特别提醒一个坑如果n0或者r0优先队列可能为空直接pop会报错。当然正常输入不会出现这种情况但OJ复习数据时保不齐有奇奇怪怪的边界可以先做一次特判。import heapq n, r map(int, input().split()) t list(map(int, input().split())) t.sort() pq [0] * r heapq.heapify(pq) ans 0 for x in t: cur heapq.heappop(pq) ans cur heapq.heappush(pq, cur x) print(ans)这段代码非常短但它体现的贪心过程是完整的。我经常跟学员说Python版因为简洁反而更容易看清算法本身在干什么每次把最小的累计时间取出来让人等这段时间然后加上自己的打水时间放回去下一个来的人又选最小的。这就是整个题目的灵魂。3.3 数据类型选择为什么一定要用long long这个坑在OJ上非常经典。n最大可能是几千甚至几万每个打水时间最大可能到几千如果不加思考直接用int总等待时间很容易爆掉。举个例子如果n10000每个人的打水时间都是1000r1那就是10000个人排队第k个人的等待时间是(k-1)×1000总等待时间是1000 × (0 1 ... 9999)大概是1000 × 5 × 10^7 5 × 10^10这已经远超int的21亿上限了。所以我在代码里一律用long longJava里是longPython不需要考虑。不少同学本机测试小数据时int完全够用交上去一WA还以为是算法错误实际上就是类型溢出。这个问题在排序类贪心题里太常见了建议养成“凡是涉及累加和默认开64位整数”的习惯。3. 蓝桥杯高频考点中的贪心算法3.1 打水问题在蓝桥杯中的定位蓝桥杯的算法提高VIP题目难度通常高于省赛基础题又低于决赛压轴题。“打水问题”几乎是贪心算法的代名词它在历年真题中反复以不同面貌出现。比如有的年份考“接水问题”第一个人排队接水后面的人要等有的年份考“排队购票”操作逻辑完全一样只是换了层皮。从考点分布来看蓝桥杯对贪心算法的考察集中在三类一是排序后按某个规则取值的简单贪心比如本题二是区间调度类比如选课问题、活动安排三是哈夫曼编码/合并石子这类树形贪心。打水问题是第一类的代表性题目做熟它后面两类也会更有感觉。很多初学者对贪心算法有一个误解觉得“贪心不就是排序嘛”。实际上排序只是实现贪心策略的手段真正的难点在于证明“按这个规则贪心一定是全局最优”。打水问题的交换证明法就是最常用的证明工具建议一定要亲手写一遍推导过程而不仅仅是背代码。3.2 从打水问题迁移到其他题目一旦理解了“短任务优先、多服务台最小负载优先”这个模型很多题都能一眼看穿。举几个实际比赛里见到的例子带权打水问题每个人打水时间不同但每个人还有一个“权重”表示单位时间等待成本。这时排序的键变成t[i] / w[i]越早处理单位成本越高的人是贪心策略的推广。区间调度问题有若干个任务每个任务有开始时间和结束时间问最多能安排几个任务。贪心策略是按结束时间排序每次选最早结束的证明方法和打水问题有异曲同工之处。多处理器调度问题要求让所有任务的总完成时间尽量短而不是等待时间最小。这时反而应该让长任务先执行和打水问题结论正好相反要注意区分目标函数。银行柜台排队问题多个柜台每个柜台服务速率不同求最低平均等待时间。如果速率不同就不只是把人按时间排序还要考虑把快的人分配给慢的柜台还是快的柜台数学上更复杂但基础还是打水问题这一套。很多同学觉得蓝桥杯真题越做越难其实难的不是新知识点而是老知识点换了新场景。打水问题就是你手里的一把钥匙能撬开很多看似无关的题。4. 常见问题与调试经验4.1 总等待时间和总完成时间是两码事这是我认为整个题目最容易出错的地方。题目求的是等待时间之和也就是每个人“等到自己开始打水”的那段时间累加。有些人写代码的时候把每个人从开始到完成的总时长也算进去这样算出的答案会大一圈而且在小数据下可能还看不出规律一旦对拍就露馅。怎么检查手算一组数据对比。比如3个人打水时间分别是1、2、3只有1个水龙头等待时间之和0 1 3 4从开始到完成的总时间1 3 6 10如果你代码输出的不是4而是10说明你把每个人自己的打水时间也算进去了。处理方式很简单累加答案的时候加的是当前水龙头的累计时间而不是累计时间加上当前人的打水时间。代码里写成ans cur而不是ans cur x这一行就是分水岭。4.2 多水龙头时排序后一定要动态选择单水龙头场景下排序完直接做前缀和就行人的顺序就是最终顺序。但多水龙头时排序只是第一步分配阶段还要每回都找当前最小累计时间的水龙头。我见过一个真实案例有个学员把所有时间排序后直接按下标i % r分给水龙头认为所有人按顺序轮流去就行。他手动模拟了n4、r2的数据时间分别是1、2、3、4。按他的逻辑1号和3号都去1号水龙头2号和4号都去2号水龙头总等待时间是0 0 1 2 3。但正确答案是0 0 1 1 2因为第4个人时间4应该排到累计时间还是1的2号水龙头而不是累计时间已经变成4的1号水龙头。这个小例子很好地解释了排序后直接按编号轮流分配在数据“正好合适”的时候可能碰巧对但一旦时间分布不均匀就错。所以不要偷懒分配阶段必须动态选。或者你干脆用优先队列版本它天然规避了这个坑。4.3 对拍验证的技巧平时练习时想验证自己的答案是否正确除了交到OJ上还可以写一个暴力全排列程序对拍。因为n比较小的时候枚举所有人打水顺序的全排列然后计算每种排列的等待时间取最小值一定是最优解。拿这个暴力和贪心程序跑同样的随机小数据结果一致基本就放心了。我给学生推荐过一个很笨但很管用的方法先自己写全排列暴力再写贪心然后用随机数生成器生成成百上千组小数据两个程序一边输出一边对比。第一次跑出不一致时把这两组数据存下来手动分析为什么贪心在这里错了。经常能发现不是贪心错而是暴力程序实现错了比如等待时间统计方式不一致。这个过程虽然费时间但能把题目理解得很透。4.4 去重与读入效率还有两个小的细节问题。第一输入时间可能有重复吗有可能。排序后重复时间不会影响正确性因为耗时相同的人谁先谁后总等待时间不变。第二蓝桥杯某些题目输入量很大比如n到了10^6级别C里建议用scanf或者关闭同步的cin否则读入可能超时。Python里用sys.stdin.readline代替input也能省不少时间。5. 从真题到竞赛思维一道题带来的提升最后聊点虚的但我觉得很重要。很多同学刷题有个误区喜欢一道一道往前冲做了很多题但遇到新题还是不会。打水问题这种经典题的价值不在于你背下了它的代码而在于你通过它掌握了一套“生活场景 - 数学模型 - 贪心策略 - 证明 - 实现”的完整链路。以后遇到任何“有n个…有m个…问怎么安排使…最小/最大”的题目第一反应不是搜题解而是先问自己三个问题目标函数是什么每一步决策有没有一个局部最优的规则这个规则能否用交换论证或反证法证明如果三个问题都能回答这道题基本上就写出来了。打水问题之所以被蓝桥杯反复选择就是因为它虽然简单但覆盖了贪心算法的完整方法论。从单水龙头到多水龙头从固定速率到不同速率只要你在基础版本上把原理吃透后续遇到各种变式都能举一反三。我个人在实际备赛中的体会是这种“一眼看穿模型”的能力比多背几十个模板更值钱。打水问题就是一个非常好的训练样本别急着写代码先拿笔在纸上把贪心过程推一遍再把交换证明写出来最后才动手写实现。多练几次这种“慢思考”到了比赛里反而能提速因为你不容易在错误的思路上浪费大量时间。