视频字幕
我们来看这样一个问题：小东、小明、小雪依次到班主任处填写表格。填写一张表格需要2分钟。小东要填写1张，小明要填写3张，小雪要填写5张。我们的目标是使三人所花的总时间最少。这里所说的总时间，是指三人的等待时间之和。也就是说，我们要合理安排他们的顺序，使得总的等待时间最短。我们先分析按小东、小明、小雪的顺序填写会怎样。小东只需要填写1张表格，耗时2分钟。小明需要填写3张，耗时6分钟。小雪需要填写5张，耗时10分钟。那么总等待时间是多少呢？小东等待2分钟，小明等待2加6等于8分钟，小雪等待2加6加10等于18分钟。总等待时间为2加8加18等于28分钟。现在我们尝试另一种顺序，按小雪、小明、小东的顺序填写。小雪需要10分钟，小明需要6分钟，小东需要2分钟。那么总等待时间是多少呢？小雪等待10分钟，小明等待10加6等于16分钟，小东等待10加6加2等于18分钟。总等待时间为10加16加18等于44分钟。通过比较，我们发现按填写表格数量从少到多的顺序安排，总等待时间最少。即先让小东填写1张表格，再让小明填写3张，最后让小雪填写5张。这样总等待时间最少为28分钟。这个问题体现了贪心算法的思想。贪心算法是指在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。在这个问题中，优先处理耗时短的任务，可以最小化总等待时间。通过合理安排顺序，可以显著减少总等待时间。按任务耗时从短到长排序，是解决此类问题的有效策略。这就是我们今天要学习的内容。