排队打水问题 #

1. 排队打水问题的介绍
2. 排队打水问题的算法分析
3. 排队打水问题代码实现

排队打水问题的介绍 #

有n个人排队到r个水龙头去打水(r<n)，他们装满水桶的时间为t1、t2、……tn为整数且各不相等，应如何安排他们的打水顺序才能使他们一共花费的时间最少？
例如有4个人到2个水龙头去打水，四个人花费的时间是2,6,4,5，如果让2,4先打水剩下的两人加一块只需等待6分钟，大家加一块需要23分钟，而如果让5,6先打水，剩下的两人加一块需要等待11分钟，大家加一块需要29分钟。

排队打水问题的算法分析 #

排队打水问题只需要使的大家等待时间最少即可，排队时越靠前面的计算次数越多，因此越小的排在前面得出的结果越小，因此此问题的贪心解答基本步骤如下：

排队打水问题的代码实现 #

an=[int(i) for i in input().split()]#n个人排队打水的时间
n=len(an)
r=int(input())#r个水龙头
minx=0#最小时间
j=0#
s=[0]*(r+1)#每一个对列时间,s[1]表示第一个列,一共有r列
an.sort()#也可自行排序
for i in range(0,n):
    j+=1
    if(j==r+1):
        j=1#前r个人为一组，第r+1个人回到第一个水龙头
    s[j]+=an[i]#加上等待时间
    minx+=s[j]#加上每一列每一个人的时间
print(minx)

小结 #

• 根据排队打水问题，理解贪心算法
• 掌握排队打水问题求解的贪心算法，能够根据实际问题作出合适的贪心策略

习题 #