蓝桥杯-排队打水问题（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 heapqn, r = map(int, input().split())
time = list(map(int, input().split()))
time.sort()# 前r个形成小根堆
waterqueue = time[:r]
heapq.heapify(waterqueue)
nextone = r
totaltime = 0while nextone<n:out = heapq.heappop(waterqueue)totaltime += outheapq.heappush(waterqueue, out+time[nextone])nextone+=1
totaltime += sum(waterqueue)
print(totaltime)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！