Question

問題：有十人各拿一只水桶去打水，如果水龍頭灌滿第i個人的水桶需要t_i分鐘，且這些t_i（i=1,2, …,10)各不相等，試問：

    若有兩個相同的水龍頭供水時，應(yīng)如何安排這十個人的次序，使他們花費的總時間最少？這個最少的總時間是多少？

Answer 1

導(dǎo)思：考慮兩個水龍頭，要注意數(shù)組的搭配與數(shù)組中的大小順序，可以聯(lián)系教材上一個水龍頭供水時的設(shè)定方法去求解.

探究：如果有兩個水龍頭，設(shè)總時間最少時有m個人在第一個水龍頭打水，設(shè)依次所需時間為p₁,p₂, …,p_m;有10-m個人在第二個水龍頭打水，依次所需時間設(shè)為q₁,q₂, …,q_10-m.顯然必有一個水龍頭的打水人數(shù)不少于5人，不妨設(shè)為第一個水龍頭，也不可能有一個水龍頭沒人去打水，則5≤m＜10.設(shè)

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.若不然，我們讓在第一個水龍頭打水的第一人到第二個水龍頭的第一位去，則總花費的時間變?yōu)椋?/p>

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

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

    即當(dāng)m＞5時，我們讓第一水龍頭的第一人到第二水龍頭去后，總時間減少.故在m=5時，總時間可能取得最小值.

    由于m=5，故兩個水龍頭人一樣多，總用時:

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

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

    不妨設(shè)p₁=t₁.下證q₁＜p₂.否則我們交換用時為q₁,p₂的兩人的位置后，總用時變?yōu)?/p>

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

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

    即經(jīng)交換后總時間變少.故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₁₀.