赞
踩
【题目描述】
有n名人员在一个水龙头前排队等候接水,每个人接水所需的时间是Ti。你的任务是通过编程找出一种排队的顺序,以使得所有人的平均等待时间最为缩短。
【输入说明】
输入包括两行内容。第一行是一个数n(1 ≤ n ≤ 1000),表示排队的人数。第二行包含n个数,分别是T1,T2,…,Tn,用空格隔开,代表每个人接水所需的时间。【输出说明】
输出也包括两行。第一行是排队顺序的一种排列,由数字1至n组成。第二行显示在这种排列下,所有人的平均等待时间,结果需要保留到小数点后两位。
- """
- [输入格式]
- 输入文件共两行,第一行为n;第二行分别表示第1个人到第n个人每人的接水时间T1,T2,…,Tn,每个数据之间有1个空格。
- [输入格式]
- 输出文件有两行,第一行为一种排队顺序,即1到n的一种排列;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
- 思路:
- 贪心算法
- 为了最小化所有人的平均等待时间,我们应该让接水时间较短的人先接水。这样,接水时间较长的人在等待时,前面的人可以更快地完成接水,从而减少总的等待时间。
- 我们可以按照每个人的接水时间将他们排序,然后计算每个人的等待时间,最后得到所有人的平均等待时间。
- """
- # code:
-
-
- def minimize_average_wait_time(n, times):
- # 创建一个列表来存储人和他们的接水时间
- people_times = list(enumerate(times, start=1))
- # 按接水时间对人进行排序
- people_times.sort(key=lambda x: x[1])
-
- # 初始化总等待时间和结果列表
- total_wait_time = 0
- result_order = []
-
- # 计算每个人的等待时间
- for i, (person, time) in enumerate(people_times):
- # 之前所有人的接水时间之和就是当前人的等待时间
- wait_time = sum(time for _, time in people_times[:i])
- total_wait_time += wait_time
- result_order.append(str(person))
-
- # 计算平均等待时间
- average_wait_time = total_wait_time / n
-
- return ' '.join(result_order), average_wait_time
-
-
- def main():
- # 输入数据
- n = int(input().strip())
- times = list(map(int, input().strip().split()))
-
- # 获取结果并打印
- order, avg_wait_time = minimize_average_wait_time(n, times)
- print(order)
- print("%.2f" % avg_wait_time)
-
-
- if __name__ == '__main__':
- main()
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。