视频字幕
我们来看这样一个问题：甲、乙、丙三人都要到同一水龙头下打水。甲需要用2分钟，乙需要用4分钟，丙需要用1分钟。怎样安排他们的顺序，才能使他们花的总时间，也就是排队和打水的时间之和最少呢？我们先来看一个错误的排队顺序：甲、乙、丙。甲打水需要2分钟，乙需要等待甲打完水，也就是2分钟，然后自己再打水4分钟，总共等待加打水是6分钟。丙则需要等待甲和乙都打完水，也就是2加4等于6分钟，然后再打水1分钟，总共是7分钟。这样算下来，三个人的总时间是2加6加7等于15分钟。那么正确的排队顺序是什么呢？我们应该让打水时间短的人先打水。所以正确的顺序是：丙、甲、乙。丙打水需要1分钟，甲需要等待丙打完水，也就是1分钟，然后自己再打水2分钟，总共等待加打水是3分钟。乙则需要等待丙和甲都打完水，也就是1加2等于3分钟，然后再打水4分钟，总共是7分钟。这样算下来，三个人的总时间是1加3加7等于11分钟。这个问题的核心在于，每个人都要等待排在他前面的人打完水。所以，打水时间短的人排在前面，可以减少后面所有人的等待时间。这就是贪心算法的思想，每次都选择当前最优的方案。从数学角度来看，如果三个人的打水时间分别是t1、t2、t3，那么总时间就是t1加t1加t2加t1加t2加t3，也就是3t1加2t2加t3。为了让总时间最小，我们应该使t1小于t2小于t3。因此，正确的排队顺序是丙、甲、乙，即按照打水时间从短到长的顺序排队。这样安排，三个人花费的总时间最少，是11分钟。