排队接水

按接水时间从小到大排序,使总等待时间最小;相同时间按编号升序。

来源 Luogu P1223 · 标签 贪心 / 排序 / 调度

题目描述

有 𝑛 个人在一个水龙头前排队接水。第 𝑖 个人接水需要 𝑇𝑖 时间,一个人的等待时间不包括自己的接水时间。

求一种排队顺序,使所有人的平均等待时间最小。若接水时间相同,编号小的人排在前面。输出该顺序和平均等待时间,平均值保留两位小数。

1≤𝑛≤1000,1≤𝑇𝑖≤106。

题解

按 (𝑇𝑖,𝑖) 升序排序。设排序后的顺序为 𝑝1,…,𝑝𝑛,则总等待时间为

𝑊=∑𝑖=1𝑛(𝑛−𝑖)𝑇𝑝𝑖.

因为第 𝑖 个人接水时,后面 𝑛−𝑖 个人都要等待 𝑇𝑝𝑖;平均等待时间为 𝑊𝑛。

若存在相邻两人 𝑇𝑥>𝑇𝑦,交换他们会使总等待时间减少 𝑇𝑥−𝑇𝑦,所以最优顺序一定按接水时间非降排列。时间相同时,交换同时间的人不影响总等待时间,取编号升序即可。

复杂度

排序为 𝑂(𝑛log𝑛);计算总等待时间为 𝑂(𝑛)。需要输出顺序,空间为 𝑂(𝑛)。

参考

源码位置