问题 1124 --【基础】学校选址

1124: 【基础】学校选址

题目描述

  

在一条笔直的公路两旁,散布着n个小区,小区里有bi个学龄儿童。但这条路上还没有学校,现准备在这条路上的任选一点(可以和小区重合,也可以不重合)建学校,使得所有学生走的路程最短。

输入

第1行:一个整数n(1 <= n <= 10000),表示公路两旁小区的数量。
接下来的n行,每行2个整数ai(0 <= ai <= 20000)和bi(1<= bi <= 10),分别表示小区的位置(将公路看成起点为0的一条数轴)和小区里学龄儿童的人数。数据保证ai互不相同。

输出

一行,2个空格隔开的整数,分别表示所选学校的位置和所有学生走的最小的路程之和。
数据保证最短的路程和只有1个。

样例输入输出

输入#1 复制
5
1 2
10 4
20 3
30 5
40 2
输出#1 复制
20 168

提示

学校选建在20这个位置,所有学生走的路程和为:19×2+10×4+10×5+20×2=168,这个路程和是最短的。

序号 标题 作者 发表时间 费用 订购数 操作