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 → stdout
输入 stdin
CtrlShiftEnter
输出 stdout

                
错误 stderr

                
CtrlEnter提交
自动保存已开启
操作成功
wzs_oj@kernel:~ — wzs-sh
guest@wzsoj:~$
刷新页面 F5
复制 Ctrl+C
粘贴 Ctrl+V
搜索题目
站点公告
今日神谕
CSP 倒计时
排行榜
我的提交
Esc 关闭 Enter 跳转 支持模糊匹配数字