一道⁺ / edao.plus

#10070

排队打水·等待时间最短

杂题四年级 #时间统筹

题目

同一个水龙头下，5 个人都要接水。他们各自接水用时分别为 1 分钟、6 分钟、3 分钟、5 分钟、4 分钟（每人只有一个水桶，水龙头一次只能供一个人用）。

现在需要安排一个接水顺序，使所有人（从开始排队到自己接完水为止）花的时间之和最少。

这个最小总时间是多少分钟？

解法

分析：要让总等待时间最少，应让用时短的人先接水。因为排在前面的人的等待时间会被后面所有人继承，所以把最短时间放在最前面，可以让更多人少等。
按时间升序排列：1、3、4、5、6 分钟。计算总等待时间。
位置系数 (按排队顺序)
=5×t₁ + 4×t₂ + 3×t₃ + 2×t₄ + 1×t₅
升序代入 1, 3, 4, 5, 6
=5×1 + 4×3 + 3×4 + 2×5 + 1×6
合计 (最小)
=5 + 12 + 12 + 10 + 6 = 45

方法

时间统筹在“能并行的就并行”的原则下，总时间由最长的那条串行链（关键路径）决定，而不是把所有任务时间相加。

练一练

6 个人排队在同一水龙头下接水，各自接水用时为 2、7、3、6、4、5 分钟。

安排合理顺序后，最少总时间（所有人各自完成接水所用时间之和）是多少分钟？

相关题目

#10071 烙饼问题·3 张饼最短时间

杂题四年级

#10167 最优化问题·烙饼问题

杂题四年级