排队接水
按接水时间从小到大排序,使总等待时间最小;相同时间按编号升序。来源 Luogu P1223 · 标签 贪心 / 排序 / 调度
题目描述
有 个人在一个水龙头前排队接水。第 个人接水需要 时间,一个人的等待时间不包括自己的接水时间。
求一种排队顺序,使所有人的平均等待时间最小。若接水时间相同,编号小的人排在前面。输出该顺序和平均等待时间,平均值保留两位小数。
,。
题解
按 升序排序。设排序后的顺序为 ,则总等待时间为
因为第 个人接水时,后面 个人都要等待 ;平均等待时间为 。
若存在相邻两人 ,交换他们会使总等待时间减少 ,所以最优顺序一定按接水时间非降排列。时间相同时,交换同时间的人不影响总等待时间,取编号升序即可。
复杂度
排序为 ;计算总等待时间为 。需要输出顺序,空间为 。
参考
- 题目链接:Luogu P1223 排队接水。