Question

有十個(gè)人各拿一只水桶去打水,設(shè)水龍頭灌滿第i個(gè)人的水桶需要t_i分鐘,且這些t_i(i=1,2,…,10)各不相等,試問:

(1)只有一只水龍頭供水時(shí),應(yīng)如何安排這十個(gè)人打水的次序,使他們的總的花費(fèi)時(shí)間最少?這個(gè)最少時(shí)間是多少?

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

Answer 1

解析：(1)設(shè)按某次序打水時(shí)水龍頭灌滿第i個(gè)人的水桶需要s_i分鐘,則第一人花費(fèi)的時(shí)間為s₁分鐘,第二人花費(fèi)的時(shí)間為(s₁+s₂)分鐘,…,第十人花費(fèi)的時(shí)間為(s₁+s₂+…+s₁₀)分鐘,總的花費(fèi)時(shí)間為s₁+(s₁+s₂)+…+(s₁+s₂+…+s₁₀)

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

其中,序列s₁,s₂,…,s₁₀是t₁,t₂,…,t₁₀的一個(gè)排列.由題設(shè),這些t_i各不相同,不妨設(shè)t₁＜t₂＜…＜t₁₀,則由排序原理知

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

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

即按任意一個(gè)次序打水花費(fèi)的總時(shí)間不小于按如下順序打水的時(shí)間:先按打水所需時(shí)間從小到大依次排隊(duì),然后逐個(gè)打水,此時(shí)花費(fèi)時(shí)間最省,總的花費(fèi)時(shí)間為(10t₁+9t₂+…+2t₉+t₁₀)分鐘.

(2)如果有兩個(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.

由(1)知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.若不然,即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í),我們讓第一個(gè)水龍頭的第一人到第二個(gè)水龍頭去后,總時(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)門″=(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＜q_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₁₀.