LG#P1223. 排队接水

排队接水

P1223 排队接水

题目描述

\hspace{15pt}有 nn 个人在一个水龙头前排队接水,假如每个人接水的时间为 tit_i,请编程找出这 nn 个人排队的一种顺序,使得 nn 个人的平均等待时间最小。

\hspace{15pt}一个人的等待时间不包括他的接水时间。

\hspace{15pt}如果两个人接水的时间相同,编号更小的人应当排在前面。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦1000)n \left(1 \leqq n \leqq 1000\right) 代表排队接水的人数。

\hspace{15pt}第二行输入 nn 个整数 $t_1, t_2, \dots, t_n \left(1 \leqq t_i \leqq 10^6\right)$,其中 tit_i 代表第 ii 个人的接水时间。

\hspace{15pt}不保证 tit_i 互不相同。

输出格式

\hspace{15pt}输出共两行。

∙ \hspace{23pt}\bullet\,第一行输出 nn 个整数,依次代表排队顺序中每个人的编号,相邻两个整数之间用空格分隔;

∙ \hspace{23pt}\bullet\,第二行输出一个实数,代表这种排队顺序下的平均等待时间,精确到小数点后两位。

测试样例

10 
56 12 1 99 1000 234 33 55 99 812
3 2 7 8 1 4 9 6 10 5
291.90

样例 1 解释

\hspace{15pt}按接水时间从小到大排列,得到的排队顺序为 3,2,7,8,1,4,9,6,10,53, 2, 7, 8, 1, 4, 9, 6, 10, 5,对应的接水时间依次为 1,12,33,55,56,99,99,234,812,10001, 12, 33, 55, 56, 99, 99, 234, 812, 1000。其中第 44 个人和第 99 个人的接水时间相同,编号更小者排在前面。此时总等待时间为 0+1+13+46+101+157+256+355+589+1401=29190+1+13+46+101+157+256+355+589+1401=2919,平均等待时间为 291910=291.90\frac{2919}{10}=291.90。