Question

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

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

Answer 1

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

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

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

總花費(fèi)的時(shí)間為：

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

首先我們來(lái)證明m=5.若不然，我們讓在第一個(gè)水龍頭打水的第一人到第二個(gè)水龍頭的第一位去，則總花費(fèi)的時(shí)間變?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時(shí)，我們讓第一水龍頭的第一人到第二水龍頭去后，總時(shí)間減少.故在m=5時(shí)，總時(shí)間可能取得最小值.

    由于m=5，故兩個(gè)水龍頭人一樣多，總用時(shí):

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

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

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

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

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

    即經(jīng)交換后總時(shí)間變少.故q₁＜p₂.也即q₁=t₂.

    類似地我們可以證明：p_i＜q_i＜p_i+1(i=1,2,3,4),p₅＜q₅.從而最省時(shí)的打水順序?yàn)椋?/p>

水龍頭一：t₁,t₃,t₅,t₇,t₉;

水龍頭二:t₂,t₄,t₆,t₈,t₁₀.

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