NOIP2010普及组「接水问题」详解：模拟算法与优先队列解法

一、问题描述

题目背景

学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。现在有 n 名同学准备接水，他们的初始接水顺序已经确定。

接水规则

1. 将这些同学按接水顺序从 1 到 n 编号，i 号同学的接水量为 wi
2. 接水开始时，1 到 m 号同学各占一个水龙头，并同时打开水龙头接水
3. 当其中某名同学 j 完成其接水量要求 wj 后，下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水
4. 这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第 x 秒结束时完成接水，则 k 同学第 x+1 秒立刻开始接水
5. 若当前接水人数 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. 模拟思路

最直观的解法是模拟法：

1. 初始化 m 个水龙头，放入前 m 个同学
2. 每秒所有正在接水的同学水量减 1
3. 如果有同学接完水（水量为 0），则从等待队列中取出下一个同学
4. 重复步骤 2-3 直到所有同学都接完水
5. 统计经过的秒数

3. 更优解法：优先队列

模拟法的时间复杂度为 O(n × max(wi))，在最坏情况下可能达到 10000 × 100 = 1,000,000 次操作，虽然可以通过，但有更优的解法。

我们可以使用**小根堆（优先队列）**来优化：

1. 初始化一个大小为 m 的小根堆，放入前 m 个同学的接水量
2. 对于剩下的 n-m 个同学：
   • 从堆顶取出最小值（最早空闲的水龙头）
   • 将当前同学的接水量加上这个最小值，然后放回堆中
3. 最后堆中的最大值就是总时间

这种方法的时间复杂度为 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;}

五、算法分析

时间复杂度

1. 模拟法：O(T × m)，其中 T 是总时间，最坏情况下 T = n × max(wi) = 10000 × 100 = 1,000,000
2. 优先队列法：O(n log m)，n ≤ 10000，m ≤ 100，log m ≈ 7，总操作约 70,000 次

空间复杂度

1. 模拟法：O(m)，只需要存储 m 个水龙头的状态
2. 优先队列法：O(m)，优先队列中最多有 m 个元素

适用场景

• 模拟法：思路直观，适合教学和理解问题
• 优先队列法：效率更高，适合竞赛和大数据量场景

六、测试验证

测试用例1

输入： 5 3 4 4 1 2 1 输出： 4

测试用例2

输入： 8 4 23 71 87 32 70 93 80 76 输出： 163

边界测试

1. m = 1（只有一个水龙头）

输入： 3 1 5 3 2 输出： 10（5+3+2）

2. m = n（水龙头数等于人数）

输入： 4 4 3 5 2 4 输出： 5（最大值）

3. wi 全部为 1

输入： 6 2 1 1 1 1 1 1 输出： 3

七、总结

本题是NOIP2010普及组的经典题目，考察了以下知识点：

1. 问题建模能力：将实际问题抽象为计算机模型
2. 模拟算法：按照规则逐步模拟过程
3. 数据结构应用：使用优先队列优化时间复杂度
4. 边界条件处理：考虑各种特殊情况

关键点总结：

1. 接水顺序固定，不能重新排序
2. 水龙头空闲时立即分配下一个同学
3. 总时间由最晚结束的水龙头决定
4. 优先队列解法将时间复杂度从 O(n × max(wi)) 优化到 O(n log m)

学习建议：

1. 先理解模拟法的思路，手动模拟样例
2. 掌握优先队列（小根堆）的使用方法
3. 思考如何将实际问题转化为算法问题
4. 在洛谷等OJ平台提交代码验证

通过这道题，我们可以学习到多任务调度问题的通用解法，这种思路在操作系统、网络传输、生产调度等领域都有广泛应用。