Question

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

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

Answer 1

导思：考虑两个水龙头，要注意数组的搭配与数组中的大小顺序，可以联系教材上一个水龙头供水时的设定方法去求解.

探究：如果有两个水龙头，设总时间最少时有m个人在第一个水龙头打水，设依次所需时间为p₁,p₂, …,p_m;有10-m个人在第二个水龙头打水，依次所需时间设为q₁,q₂, …,q_10-m.显然必有一个水龙头的打水人数不少于5人，不妨设为第一个水龙头，也不可能有一个水龙头没人去打水，则5≤m＜10.设

p₁＜p₂＜…＜p_m，q₁＜q₂＜…＜q_10-m.

总花费的时间为：

T=mp₁+(m-1)p₂+…+p_m+(10-m)q₁+(9-m)q₂+…+q_10-m.

其中{p₁,p₂, …,p_m,q₁,q₂, …,q_10-m}={t₁,t₂, …,t₁₀},t₁＜t₂＜…＜t₁₀.

首先我们来证明m=5.若不然，我们让在第一个水龙头打水的第一人到第二个水龙头的第一位去，则总花费的时间变为：

T′=(m-1)p₂+…+p_m+(11-m)p₁+(10-m)q₁+…+q_10-m.

T-T′=(2m-11)p₁＞0.

    即当m＞5时，我们让第一水龙头的第一人到第二水龙头去后，总时间减少.故在m=5时，总时间可能取得最小值.

    由于m=5，故两个水龙头人一样多，总用时:

T=(5p₁+4p₂+3p₃+2p₄+p₅)+(5q₁+4q₂+3q₃+2q₄+q₅).

    由于p₁＜p₂＜…＜p₅,q₁＜q₂＜…＜q₅.

    不妨设p₁=t₁.下证q₁＜p₂.否则我们交换用时为q₁,p₂的两人的位置后，总用时变为

T″=(5p₁+4q₁+3p₃+2p₄+p₅)+(5p₂+4q₂+3q₃+2q₄+q₅),

T-T″=q₁-p₂＞0.

    即经交换后总时间变少.故q₁＜p₂.也即q₁=t₂.

    类似地我们可以证明：p_i＜q_i＜p_i+1(i=1,2,3,4),p₅＜q₅.从而最省时的打水顺序为：

水龙头一：t₁,t₃,t₅,t₇,t₉;

水龙头二:t₂,t₄,t₆,t₈,t₁₀.

其中：t₁＜t₂＜…＜t₁₀.