NOIP2010普及组「接水问题」详解：模拟算法与优先队列解法
一、问题描述
题目背景
学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。现在有 n 名同学准备接水，他们的初始接水顺序已经确定。
接水规则
- 将这些同学按接水顺序从 1 到 n 编号，i 号同学的接水量为 wi
- 接水开始时，1 到 m 号同学各占一个水龙头，并同时打开水龙头接水
- 当其中某名同学 j 完成其接水量要求 wj 后，下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水
- 这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第 x 秒结束时完成接水，则 k 同学第 x+1 秒立刻开始接水
- 若当前接水人数 n’ 不足 m，则只有 n’ 个龙头供水，其它 m−n’ 个龙头关闭
输入输出格式
输入格式：
- 第 1 行：2 个整数 n 和 m，用一个空格隔开，分别表示接水人数和龙头个数
- 第 2 行：n 个整数 w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示 i 号同学的接水量
输出格式：
- 一行，1 个整数，表示接水所需的总时间
数据范围
- 1 ≤ n ≤ 10000
- 1 ≤ m ≤ 100 且 m ≤ n
- 1 ≤ wi ≤ 100
二、样例分析
样例1
输入： 5 3 4 4 1 2 1 输出： 4样例说明：
第 1 秒，3 人接水。第 1 秒结束时，1、2、3 号同学每人的已接水量为 1，3 号同学接完水，4 号同学接替 3 号同学开始接水。
第 2 秒，3 人接水。第 2 秒结束时，1、2 号同学每人的已接水量为 2，4 号同学的已接水量为 1。
第 3 秒，3 人接水。第 3 秒结束时，1、2 号同学每人的已接水量为 3，4 号同学的已接水量为 2。4 号同学接完水，5 号同学接替 4 号同学开始接水。
第 4 秒，3 人接水。第 4 秒结束时，1、2 号同学每人的已接水量为 4，5 号同学的已接水量为 1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为 4 秒。
样例2
输入： 8 4 23 71 87 32 70 93 80 76 输出： 163三、问题分析
1. 理解题意
这是一个典型的多任务并行处理问题，类似于操作系统中的进程调度。关键点在于：
- 接水顺序固定，不能随意调整
- m 个水龙头可以同时工作
- 当一个水龙头空闲时，立即从等待队列中取出下一个同学
- 需要计算所有同学都接完水所需的总时间
2. 模拟思路
最直观的解法是模拟法：
- 初始化 m 个水龙头，放入前 m 个同学
- 每秒所有正在接水的同学水量减 1
- 如果有同学接完水（水量为 0），则从等待队列中取出下一个同学
- 重复步骤 2-3 直到所有同学都接完水
- 统计经过的秒数
3. 更优解法：优先队列
模拟法的时间复杂度为 O(n × max(wi))，在最坏情况下可能达到 10000 × 100 = 1,000,000 次操作，虽然可以通过，但有更优的解法。
我们可以使用**小根堆（优先队列）**来优化：
- 初始化一个大小为 m 的小根堆，放入前 m 个同学的接水量
- 对于剩下的 n-m 个同学：
- 从堆顶取出最小值（最早空闲的水龙头）
- 将当前同学的接水量加上这个最小值，然后放回堆中
- 最后堆中的最大值就是总时间
这种方法的时间复杂度为 O(n log m)，更加高效。
四、算法实现
方法一：模拟法（直接模拟每秒过程）
#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,m;cin>>n>>m;vector<int>w(n);for(inti=0;i<n;i++){cin>>w[i];}// 初始化水龙头，放入前m个同学vector<int>taps(m,0);for(inti=0;i<m&&i<n;i++){taps[i]=w[i];}intnext=m;// 下一个要接水的同学索引inttime=0;while(true){time++;// 所有水龙头水量减1for(inti=0;i<m;i++){if(taps[i]>0){taps[i]--;// 如果这个同学接完了if(taps[i]==0){// 还有同学等待，就安排下一个if(next<n){taps[i]=w[next];next++;}}}}// 检查是否所有人都接完了boolallDone=true;for(inti=0;i<m;i++){if(taps[i]>0){allDone=false;break;}}if(allDone&&next>=n){break;}}cout<<time<<endl;return0;}方法二：优先队列优化法
#include<iostream>#include<vector>#include<queue>usingnamespacestd;intmain(){intn,m;cin>>n>>m;vector<int>w(n);for(inti=0;i<n;i++){cin>>w[i];}// 使用小根堆（优先队列）priority_queue<int,vector<int>,greater<int>>pq;// 初始化：前m个同学开始接水for(inti=0;i<m&&i<n;i++){pq.push(w[i]);}// 处理剩下的同学for(inti=m;i<n;i++){intearliest=pq.top();// 最早空闲的水龙头时间pq.pop();pq.push(earliest+w[i]);// 当前同学在这个水龙头接水}// 找出最大的时间intmaxTime=0;while(!pq.empty()){maxTime=max(maxTime,pq.top());pq.pop();}cout<<maxTime<<endl;return0;}方法三：更简洁的优先队列写法
#include<iostream>#include<queue>#include<vector>#include<algorithm>usingnamespacestd;intmain(){intn,m;cin>>n>>m;priority_queue<int,vector<int>,greater<int>>pq;// 先放入m个0，表示m个水龙头初始空闲for(inti=0;i<m;i++){pq.push(0);}intmaxTime=0;for(inti=0;i<n;i++){intw;cin>>w;intearliest=pq.top();pq.pop();intfinishTime=earliest+w;pq.push(finishTime);maxTime=max(maxTime,finishTime);}cout<<maxTime<<endl;return0;}五、算法分析
时间复杂度
- 模拟法：O(T × m)，其中 T 是总时间，最坏情况下 T = n × max(wi) = 10000 × 100 = 1,000,000
- 优先队列法：O(n log m)，n ≤ 10000，m ≤ 100，log m ≈ 7，总操作约 70,000 次
空间复杂度
- 模拟法：O(m)，只需要存储 m 个水龙头的状态
- 优先队列法：O(m)，优先队列中最多有 m 个元素
适用场景
- 模拟法：思路直观，适合教学和理解问题
- 优先队列法：效率更高，适合竞赛和大数据量场景
六、测试验证
测试用例1
输入： 5 3 4 4 1 2 1 输出： 4测试用例2
输入： 8 4 23 71 87 32 70 93 80 76 输出： 163边界测试
- m = 1（只有一个水龙头）
输入： 3 1 5 3 2 输出： 10（5+3+2）- m = n（水龙头数等于人数）
输入： 4 4 3 5 2 4 输出： 5（最大值）- wi 全部为 1
输入： 6 2 1 1 1 1 1 1 输出： 3七、总结
本题是NOIP2010普及组的经典题目，考察了以下知识点：
- 问题建模能力：将实际问题抽象为计算机模型
- 模拟算法：按照规则逐步模拟过程
- 数据结构应用：使用优先队列优化时间复杂度
- 边界条件处理：考虑各种特殊情况
关键点总结：
- 接水顺序固定，不能重新排序
- 水龙头空闲时立即分配下一个同学
- 总时间由最晚结束的水龙头决定
- 优先队列解法将时间复杂度从 O(n × max(wi)) 优化到 O(n log m)
学习建议：
- 先理解模拟法的思路，手动模拟样例
- 掌握优先队列（小根堆）的使用方法
- 思考如何将实际问题转化为算法问题
- 在洛谷等OJ平台提交代码验证
通过这道题，我们可以学习到多任务调度问题的通用解法，这种思路在操作系统、网络传输、生产调度等领域都有广泛应用。