2326. 魔法学院的“急诊”答疑
1000ms
256MB
简单
贪心算法
题目描述
在霍格沃茨魔法学院,龙老师的信息奥赛课那可是座无虚席。每天午休时间,办公室门口都会排起长龙,学生们个个拿着羊皮纸等着龙老师答疑。
有的同学问题简单,点拨一下只需 1 分钟;有的同学钻了牛角尖,非得龙老师讲上 10 分钟不可。为了不让大家在走廊里等得太心急,助理老师想了个法子:他预估了每个学生所需的答疑时长,并写在纸条上。
龙老师希望你帮忙设计一个排队顺序,使得所有学生平均等待及完成答疑的时间之和最少。
**注意**:每个人的“答疑完成时间” = 自己的答疑时长 + 等待前面所有同学的时间。
输入格式
- 第一行包含一个正整数 $n$ ($n \le 1000$),表示学生数量。
- 第二行包含 $n$ 个正整数,表示每个学生的预估答疑时长 $t_i$ ($t_i \le 2000$)。
输出格式
- 输出一个实数,表示最少的平均答疑完成时间,结果保留两位小数。
样例 1
输入 (Input)
4 3 1 2 6
输出 (Output)
5.50
样例说明
时长分别为 `3, 1, 2, 6`。
最优顺序为从小到大:`1, 2, 3, 6`。
- 第 1 个人完成时间:1
- 第 2 个人完成时间:1 + 2 = 3
- 第 3 个人完成时间:1 + 2 + 3 = 6
- 第 4 个人完成时间:1 + 2 + 3 + 6 = 12
- 平均完成时间:$(1 + 3 + 6 + 12) / 4 = 22 / 4 = 5.50$。
- $n \le 1000$,$t_i \le 2000$。
这是一个经典的**贪心算法**问题。为了让总的等待时间最少,应该让答疑时间短的同学排在前面。
1. 将所有答疑时间从小到大排序。
2. 依次计算每个人的完成时间并求和,最后除以总人数 $n$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功