问题：有十人各拿一只水桶去打水，如果水龙头灌满第i个人的水桶需要ti分钟，且这些ti（i=12…10)各不相等，试问：若有两个相同的水龙头供水时，应如何安排这十个人的

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 ₁₀ .