Question

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

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

Answer 1

答案：
解析：

導思：考慮兩個水龍頭，要注意數組的搭配與數組中的大小順序，可以聯系教材上一個水龍頭供水時的設定方法去求解． 　　探究：如果有兩個水龍頭，設總時間最少時有m個人在第一個水龍頭打水，設依次所需時間為p1，p2，…，pm；有10－m個人在第二個水龍頭打水，依次所需時間設為q1，q2，…，q10－m．顯然必有一個水龍頭的打水人數不少于5人，不妨設為第一個水龍頭，也不可能有一個水龍頭沒人去打水，則5≤m＜10．設 　　p1＜p2＜…＜pm，q1＜q2＜…＜q10－m． 　　總花費的時間為： 　　T＝mp1＋(m－1)p2＋…＋pm＋(10－m)q1＋(9－m)q2＋…＋q10－m． 　　其中{p1，p2，…，pm，q1，q2，…，q10－m}＝{t1，t2，…，t10}，t1＜t2＜…＜t10． 　　首先我們來證明m＝5．若不然，我們讓在第一個水龍頭打水的第一人到第二個水龍頭的第一位去，則總花費的時間變為：