A B C D 四人分别拿着4 3 2 1 个暖瓶去打开水,热水龙头只有一个,假如打满一瓶水需要一分钟,怎么安排他们打水

4个回答

  • 答:

    将题目一般化,设有x1,x2,...xn号人拿着1,2,...n个暖水瓶

    打水,设a1,a2,...an是x1,x2,...xn的一个排列,即代表

    a1号第一个打水,...an号最后一个打水,依此类推,

    并且a1,a2,...an号打水所需时间为y1,y2,...yn,则y1,y2,...yn

    是1到n的一个排列,由题意所需总时间

    S=y1+(y1+y2)+...+(y1+y2+...+yn)

    =ny1+(n-1)y2+(n-2)y3+...+2y(n-1)+yn

    S可以看成1到n的一个排列(n,n-1,...1)

    与1到n的一个排列(y1,y2,...yn)逐项乘积,

    现介绍一个排序不等式

    设有两组数满足M1≤M2≤...≤Mn

    和K1≤K2≤...≤Kn

    则有倒序和≤乱序和≤正序和

    举个例子,M1≤M2≤M3

    K1≤K1≤K3,则有

    M1*K3+M2*K2+M3*K1≤M1*K2+M2*K3+M3*K1≤M1*K1+M2*K2+M3*K3

    由上可知,当y1,y2,...yn为1,2,...n时S取到最小值

    S的最小值为Smin=1*n+2*(n-1)+...+(n-1)*2+n*1

    Smin=n(n+1)(n+2)/6,

    将n=4代入知道本题打水时间总和最小为20分钟,

    打水顺序是D→C→B→A,

    从上可知要想打水时间总和最少,

    应该让净打水时间(不算上等待时间)

    少的人排在净打水时间多的人前面.

相关问题