描述
有 $ n $ 个人在一个水龙头前排队接水。每个人接水所需的时间为 $ T_i $。
请你安排一种排队顺序,使得所有人的平均等待时间最小。
- 等待时间:每个人从开始排队到轮到自己接水所花费的时间(不包括自己接水的时间)。
- 总等待时间 = 第1个人等待0 + 第2个人等待 $ T_1 $ + 第3个人等待 $ T_1 + T_2 + … $
- 平均等待时间 = 总等待时间 / $ n $。
请输出最优的排队顺序(按原编号排列)以及对应的平均等待时间,精确到小数点后两位。
输入
- 第一行包含一个整数 $ n ( 1 \le n \le 1000 )$,表示人数。
- 第二行包含 $ n $ 个正整数 $ T_1, T_2, \dots, T_n ,( 1 \le T_i \le 1000 )$,表示每个人接水所需的时间。
输出
- 第一行输出 $ n $ 个整数,表示最优排队顺序(原始编号),编号从 1 开始,每两个数之间用一个空格隔开。
- 第二行输出一个实数,表示最小平均等待时间,保留两位小数。
样例
- 复制
- 复制
提示
### 样例说明
- 按接水时间从小到大排序,对应编号顺序为 3(1), 2(12), 7(33), 8(55), 1(56), 4(99), 9(99), 6(234), 10(812), 5(1000)。
- 总等待时间 = 0 + 1 + 13 + 46 + 101 + 157 + 256 + 355 + 589 + 1401 = 2919?实际计算:按顺序,等待时间分别为:0, 1, 1+12=13, 13+33=46, 46+55=101, 101+56=157, 157+99=256, 256+99=355, 355+234=589, 589+812=1401,总和 = 0+1+13+46+101+157+256+355+589+1401 = 2919。平均 = 2919/10 = 291.9,输出 291.90。
## 数据范围与约定
- $ 1 \le n \le 1000 $
- $ 1 \le T_i \le 1000 $

关注我们