首页 / 题库

P13075 - 排队接水

算法入门
通过次数36 提交次数49 内存限制 64MB 时间限制1秒

描述

有 $ 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 $

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36