Question

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

(1)只有一只水龙头供水时,应如何安排这十个人打水的次序,使他们的总的花费时间最少?这个最少时间是多少?

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

Answer 1

解析：(1)设按某次序打水时水龙头灌满第i个人的水桶需要s_i分钟,则第一人花费的时间为s₁分钟,第二人花费的时间为(s₁+s₂)分钟,…,第十人花费的时间为(s₁+s₂+…+s₁₀)分钟,总的花费时间为s₁+(s₁+s₂)+…+(s₁+s₂+…+s₁₀)

=10s₁+9s₂+…+2s₉+s₁₀.

其中,序列s₁,s₂,…,s₁₀是t₁,t₂,…,t₁₀的一个排列.由题设,这些t_i各不相同,不妨设t₁＜t₂＜…＜t₁₀,则由排序原理知

10s₁+9s₂+…+2s₉+s₁₀

≥10t₁+9t₂+…+2t₉+t₁₀，

即按任意一个次序打水花费的总时间不小于按如下顺序打水的时间:先按打水所需时间从小到大依次排队,然后逐个打水,此时花费时间最省,总的花费时间为(10t₁+9t₂+…+2t₉+t₁₀)分钟.

(2)如果有两个水龙头,设总时间最少时有m个人在第一个水龙头打水,设依次所用时间为p₁,p₂,…,p_m;有10-m个人在第二个水龙头打水,依次所需时间设为q₁,q₂,…,q_10-m.

显然必有一个水龙头的打水人数不少于5人,不妨设为第一个水龙头,也不可能有一个水龙头没人去打水,则5≤m＜10.

由(1)知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.若不然,即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＜q_i+1(i=1,2,3,4),p₅＜q₅.从而最省时的打水顺序为

水龙头一:t₁,t₃,t₅,t₇,t₉;水龙头二:t₂,t₄,t₆,t₈,t₁₀.其中t₁＜t₂＜…＜t₁₀.