s09208. 加权仓址 · 林老师的题库

题目描述

数轴上有一排 $n$ 个仓位，仓位 $i$ 位于坐标 $a_{i}$ ，每天有 $w_{i}$ 车货要从仓位 $i$ 运往新仓库。你要在数轴上选一个整数坐标 $x$ 建仓库，使总运量

i = 1 \sum n w_{i} \cdot ∣ a_{i} - x ∣

最小。输出这个最小值。

第一行一个整数 $n$ 。

接下来 $n$ 行，第 $i$ 行两个整数 $a_{i}, w_{i}$ 。

一行一个整数，最小的总运量。

输入

输出

选 $x = 3$ 时运量为 $∣1 - 3∣ + ∣3 - 3∣ + ∣5 - 3∣ = 4$ ，可以验证没有更小的方案。