核心思想
这个问题可以看成是 多台机器(水龙头)按固定顺序处理作业(同学) 的调度问题。
因为接水顺序已经固定,且每个水龙头出水速度相同(每秒 1 单位),所以我们可以不模拟每一秒,而是用事件驱动的方式,只关心每个水龙头什么时候完成当前任务。
具体过程
初始化
有 m 个水龙头,一开始都是空闲的,所以它们当前“完成时间”都为 0(即第 0 秒时都可用)。
按顺序安排每个同学
对于第 i 个同学(接水量为 w_i):
从所有水龙头中,找出当前完成时间最小的那个(也就是最早空闲的水龙头)。
让这个同学使用该水龙头,那么该水龙头的完成时间就会增加 w_i(因为从它空闲那一刻起,要花 w_i 秒来接完这个同学的水)。
更新这个水龙头的完成时间为 原时间 + w_i。
重复直到所有同学安排完毕
这样,每个同学都会被分配到当时最早空闲的水龙头上,完全符合题目中“有人接完,下一个马上补上”的规则。
得出总时间
当所有同学都安排完后,m 个水龙头各自都有一个“最终完成时间”。
因为所有水龙头是同时工作的,所以总耗时就是这些完成时间中的最大值。
(原因:只有最后一个水龙头停止工作时,所有人才都接完水。)
如何高效实现?
可以用一个小根堆(优先队列)来存储每个水龙头的当前完成时间。
每次取堆顶(最小值),加上当前同学的接水量,再放回堆中。
时间复杂度:O(n log m),n 最多 1e4,m 最多 100,完全足够。
当然,因为 m 很小,你也可以直接用数组每次扫描找最小值,复杂度 O(n*m),也完全可行。
举个简单例子
比如 n=5, m=3,水量依次为 4 4 1 2 1:
初始三个水龙头时间:[0,0,0]
同学1(4):取0→变成4,堆:[0,0,4](实际排序后为[0,0,4])
同学2(4):取0→变成4,堆:[0,4,4]
同学3(1):取0→变成1,堆:[1,4,4]
同学4(2):取1→变成3,堆:[3,4,4]
同学5(1):取3→变成4,堆:[4,4,4]
最终最大值为 4,所以总时间 4 秒。与样例一致。