P1223 排队接水
题目描述
有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 ti,请编程找出这 n 个人排队的一种顺序,使得 n 个人的平均等待时间最小。
一个人的等待时间不包括他的接水时间。
如果两个人接水的时间相同,编号更小的人应当排在前面。
输入格式
第一行输入一个整数 n(1≦n≦1000) 代表排队接水的人数。
第二行输入 n 个整数 $t_1, t_2, \dots, t_n \left(1 \leqq t_i \leqq 10^6\right)$,其中 ti 代表第 i 个人的接水时间。
不保证 ti 互不相同。
输出格式
输出共两行。
∙第一行输出 n 个整数,依次代表排队顺序中每个人的编号,相邻两个整数之间用空格分隔;
∙第二行输出一个实数,代表这种排队顺序下的平均等待时间,精确到小数点后两位。
测试样例
10
56 12 1 99 1000 234 33 55 99 812
3 2 7 8 1 4 9 6 10 5
291.90
样例 1 解释
按接水时间从小到大排列,得到的排队顺序为 3,2,7,8,1,4,9,6,10,5,对应的接水时间依次为 1,12,33,55,56,99,99,234,812,1000。其中第 4 个人和第 9 个人的接水时间相同,编号更小者排在前面。此时总等待时间为 0+1+13+46+101+157+256+355+589+1401=2919,平均等待时间为 102919=291.90。