一、问题描述题目背景学校里有一个水房水房里一共装有 m 个龙头可供同学们打开水每个龙头每秒钟的供水量相等均为 1。现在有 n 名同学准备接水他们的初始接水顺序已经确定。接水规则将这些同学按接水顺序从 1 到 n 编号i 号同学的接水量为 wi接水开始时1 到 m 号同学各占一个水龙头并同时打开水龙头接水当其中某名同学 j 完成其接水量要求 wj 后下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水这个换人的过程是瞬间完成的且没有任何水的浪费。即 j 同学第 x 秒结束时完成接水则 k 同学第 x1 秒立刻开始接水若当前接水人数 n’ 不足 m则只有 n’ 个龙头供水其它 m−n’ 个龙头关闭输入输出格式输入格式第 1 行2 个整数 n 和 m用一个空格隔开分别表示接水人数和龙头个数第 2 行n 个整数 w1、w2、……、wn每两个整数之间用一个空格隔开wi 表示 i 号同学的接水量输出格式一行1 个整数表示接水所需的总时间数据范围1 ≤ n ≤ 100001 ≤ m ≤ 100 且 m ≤ n1 ≤ wi ≤ 100二、样例分析样例1输入 5 3 4 4 1 2 1 输出 4样例说明第 1 秒3 人接水。第 1 秒结束时1、2、3 号同学每人的已接水量为 13 号同学接完水4 号同学接替 3 号同学开始接水。第 2 秒3 人接水。第 2 秒结束时1、2 号同学每人的已接水量为 24 号同学的已接水量为 1。第 3 秒3 人接水。第 3 秒结束时1、2 号同学每人的已接水量为 34 号同学的已接水量为 2。4 号同学接完水5 号同学接替 4 号同学开始接水。第 4 秒3 人接水。第 4 秒结束时1、2 号同学每人的已接水量为 45 号同学的已接水量为 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)更加高效。四、算法实现方法一模拟法直接模拟每秒过程#includeiostream#includevectorusingnamespacestd;intmain(){intn,m;cinnm;vectorintw(n);for(inti0;in;i){cinw[i];}// 初始化水龙头放入前m个同学vectorinttaps(m,0);for(inti0;imin;i){taps[i]w[i];}intnextm;// 下一个要接水的同学索引inttime0;while(true){time;// 所有水龙头水量减1for(inti0;im;i){if(taps[i]0){taps[i]--;// 如果这个同学接完了if(taps[i]0){// 还有同学等待就安排下一个if(nextn){taps[i]w[next];next;}}}}// 检查是否所有人都接完了boolallDonetrue;for(inti0;im;i){if(taps[i]0){allDonefalse;break;}}if(allDonenextn){break;}}couttimeendl;return0;}方法二优先队列优化法#includeiostream#includevector#includequeueusingnamespacestd;intmain(){intn,m;cinnm;vectorintw(n);for(inti0;in;i){cinw[i];}// 使用小根堆优先队列priority_queueint,vectorint,greaterintpq;// 初始化前m个同学开始接水for(inti0;imin;i){pq.push(w[i]);}// 处理剩下的同学for(intim;in;i){intearliestpq.top();// 最早空闲的水龙头时间pq.pop();pq.push(earliestw[i]);// 当前同学在这个水龙头接水}// 找出最大的时间intmaxTime0;while(!pq.empty()){maxTimemax(maxTime,pq.top());pq.pop();}coutmaxTimeendl;return0;}方法三更简洁的优先队列写法#includeiostream#includequeue#includevector#includealgorithmusingnamespacestd;intmain(){intn,m;cinnm;priority_queueint,vectorint,greaterintpq;// 先放入m个0表示m个水龙头初始空闲for(inti0;im;i){pq.push(0);}intmaxTime0;for(inti0;in;i){intw;cinw;intearliestpq.top();pq.pop();intfinishTimeearliestw;pq.push(finishTime);maxTimemax(maxTime,finishTime);}coutmaxTimeendl;return0;}五、算法分析时间复杂度模拟法O(T × m)其中 T 是总时间最坏情况下 T n × max(wi) 10000 × 100 1,000,000优先队列法O(n log m)n ≤ 10000m ≤ 100log 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 输出 10532m 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平台提交代码验证通过这道题我们可以学习到多任务调度问题的通用解法这种思路在操作系统、网络传输、生产调度等领域都有广泛应用。