分数: 400 分
问题陈述
高桥在一家建筑管理公司工作。他管理的大楼有 N 房间,房间在哪里 i (1 \leq i \leq N)的大小为 S_i 和当前温度 P_i ℃.
高桥想要将所有房间的温度统一为相同的整数值 T ℃。升高或降低房间温度的成本 i by 1 ℃为 S_i 在任何一种情况下。即改变房间温度的成本 i 来自 P_i ℃至 T ℃为 S_i \times |P_i - T|.
高桥可自由选择目标温度 T 为任何整数。求总成本的最小值,将所有房间的温度统一到 T ℃:
\sum_{i=1}^{N} S_i \times |P_i - T|
约束
- 1 \leq N \leq 150000
- 1 \leq S_i \leq 10^4
- -10^9 \leq P_i \leq 10^9
- 所有输入值均为整数。
输入
N S_1 P_1 S_2 P_2 \vdots S_N P_N
- 第一行包含一个整数 N 代表房间数量。
- 的 i- 以下各项 N 行包含大小 S_i 和当前温度 房间的 P_i 房间的 i,用空格分隔。
输出
在单行中输出将所有房间的温度统一为相同整数值的最小总成本(作为整数)。
示例输入 1
3 2 18 1 23 2 20
示例输出 1
7
示例输入 2
2 5 0 5 10
示例输出 2
50
示例输入 3
8 3 -5 2 0 6 4 1 -2 5 10 4 4 2 7 3 -5
示例输出 3
104
示例输入 4
15 8 12 5 -3 7 7 4 7 10 20 6 -10 3 0 9 15 2 -3 1 100 8 12 5 30 7 -20 4 15 6 7
示例输出 4
879
示例输入 5
1 10000 -1000000000
示例输出 5
0