P4264 [USACO18FEB] Teleportation S

题目描述

Farmer John 最不喜欢的农活之一就是到处搬运牛粪。为了简化这一过程，他发明了一个绝妙的装置：牛粪传送器！与其用拖拉机后面的拖车搬运牛粪，他可以使用牛粪传送器将牛粪从一个位置瞬间传送到另一个位置。

Farmer John 的农场建在一条笔直的长路上，因此农场上的任何位置都可以简单地用其在这条路上的位置来描述（实际上就是数轴上的一个点）。传送器由两个数字 $x$ 和 $y$ 描述，其中被带到位置 $x$ 的牛粪可以瞬间传送到位置 $y$。

Farmer John 决定建造一个传送器，其第一个端点位于 $x = 0$；你的任务是帮助他确定另一个端点 $y$ 的最佳选择。特别地，农场上有 $N$ 堆牛粪（$1 \leq N \leq 100,000$）。第 $i$ 堆牛粪需要从位置 $a_i$ 搬运到位置 $b_i$，Farmer John 会分别搬运每一堆牛粪。如果我们用 $d_i$ 表示 Farmer John 搬运第 $i$ 堆牛粪时拖拉机行驶的距离，那么如果他直接用拖拉机搬运第 $i$ 堆牛粪，则 $d_i = |a_i - b_i|$；如果他使用传送器，则 $d_i$ 可能会更小（例如，通过用拖拉机从 $a_i$ 运到 $x$，然后从 $y$ 运到 $b_i$）。

请帮助 Farmer John 确定通过将传送器的另一个端点 $y$ 建在一个精心选择的最优位置，可以实现的最小 $d_i$ 总和。搬运每堆牛粪时使用相同的 $y$ 位置。

输入格式

输入的第一行包含 $N$。接下来的 $N$ 行中，第 $i$ 行包含 $a_i$ 和 $b_i$，每个整数的范围在 $-10^8 \ldots 10^8$ 之间。这些值不一定全部不同。

输出格式

输出一个数字，表示 Farmer John 可以实现的最小 $d_i$ 总和。请注意，这个数字可能超过标准 32 位整数的范围，因此可能需要使用更大的整数类型，例如 C/C++ 中的 long long。此外，你可能需要考虑答案是否一定是整数……

输入输出样例 1

3
-5 -7
-3 10
-2 7

10

说明/提示

在这个例子中，通过设置 $y = 8$，Farmer John 可以实现 $d_1 = 2$、$d_2 = 5$ 和 $d_3 = 3$。请注意，$y$ 在范围 $[7,10]$ 内的任何值也会产生最优解。

题目来源：Brian Dean