蓝桥杯 算法提高 排队打水问题 Python_python打水问题

算法提高 排队打水问题

时间限制：1.0s 内存限制：256.0MB

问题描述
　　有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…………tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
　　
输入格式
　　第一行n，r (n<=500,r<=75)
　　第二行为n个人打水所用的时间Ti (Ti<=100)；
　　
输出格式
　　最少的花费时间
　　
样例输入
3 2
1 2 3

样例输出
7

数据规模和约定
　　其中80%的数据保证n<=10

思路：
这是贪心算法的题，要找出一个贪心标准，可以一步步求出局部最优解，最后得出最优解；这里我选取的策略是打水花费时间最短的人先打水。

1. 首先 排序-最先打水的人，并在此水龙头上记录花费时间，因为后面有人会排队

2. 再考虑-两个水龙头，当前正在使用水龙头的人中，时间短的那个人肯定先打完，后面的人肯定也要先排到这个水龙头后面

代码：

# 贪心
N, R = input().split()
ti = list(map(int, input().split()))

ti = sorted(ti) # 贪心策略：打水时间最短的人先打水

wait = [0] * int(R) # 水龙头使用的时间
summ = 0

for i in range(int(N)):
    wait = sorted(wait) # 从小到大排序，最小值的水龙头肯定是相对先使用完的
    summ += wait[0] + ti[i]
    wait[0] += ti[i]

print(summ)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16