蓝桥杯-排队打水问题（python，优先队列）

蓝桥杯-排队打水问题

一、题目描述二、思路和代码

思路：代码：

  有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…………tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入
第一行n，r (n< =500,r< =75)
第二行为n个人打水所用的时间Ti (Ti< =100)；

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

输出
最少的花费时间
样例输入

3 2
1 2 3

样例输出

7

  因为问题具有最优子结构，前面的决策不影响后序结果的性质，考虑使用贪心算法，每次都让打水时间最短的人先打水。
贪心法正确性证明很简单，用反证法。因为总打水时间包括实际每人打水时间之和（打水时间序列和s1，不变）和所有人的等待时间之和（是打水时间序列组成的可重复序列和s2，可变）。假若总时长最优队列的末尾不是时间最长的，则可以通过将其与排在前面的打水最长时间之人交换位置，得到一个新的s2‘，显然s2’ 代码：

  于是问题主要化成求解总时长，用python自带优先队列heapq的方式实现简单高效。

# 用贪心算法，短则优先,用优先队列（小根堆）
import heapq


n, r = map(int, input().split())
time = list(map(int, input().split()))
time.sort()


# 前r个形成小根堆
waterqueue = time[:r]
heapq.heapify(waterqueue)
nextone = r
totaltime = 0

while nextone