Question

有十人各拿一只水桶去打水，如果水龙头灌满第i个人的水桶需要t_i分钟，且这些t_i(i＝1，2，…，10)各不相等，试问：

若有两个相同的水龙头供水时，应如何安排这十个人的次序，使他们花费的总时间最少？这个最少的总时间是多少？

Answer 1

答案：
解析：

导思：考虑两个水龙头，要注意数组的搭配与数组中的大小顺序，可以联系教材上一个水龙头供水时的设定方法去求解． 　　探究：如果有两个水龙头，设总时间最少时有m个人在第一个水龙头打水，设依次所需时间为p1，p2，…，pm；有10－m个人在第二个水龙头打水，依次所需时间设为q1，q2，…，q10－m．显然必有一个水龙头的打水人数不少于5人，不妨设为第一个水龙头，也不可能有一个水龙头没人去打水，则5≤m＜10．设 　　p1＜p2＜…＜pm，q1＜q2＜…＜q10－m． 　　总花费的时间为： 　　T＝mp1＋(m－1)p2＋…＋pm＋(10－m)q1＋(9－m)q2＋…＋q10－m． 　　其中{p1，p2，…，pm，q1，q2，…，q10－m}＝{t1，t2，…，t10}，t1＜t2＜…＜t10． 　　首先我们来证明m＝5．若不然，我们让在第一个水龙头打水的第一人到第二个水龙头的第一位去，则总花费的时间变为：