Teleportation

题目描述

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$ 表示 FJ 用拖拉机装载第 $i$ 堆牛粪行驶的距离，那么如果他直接用拖拉机运输第 $i$ 堆，可能有 $d_i = |a_i-b_i|$；而如果他使用传送器，$d_i$ 可能更小（例如，先用拖拉机把牛粪从 $a_i$ 运到 $x$，再从 $y$ 运到 $b_i$）。

请帮助 FJ 确定：通过精心选择传送器另一端点 $y$ 的位置，他所能达到的 $d_i$ 之和的最小可能值。运输每一堆时使用的都是同一个位置 $y$。

输入格式

输入格式（文件 teleport.in）： 第一行包含 $N$。接下来的 $N$ 行中，第 $i$ 行包含 $a_i$ 和 $b_i$，它们都是范围 $-10^8 \ldots 10^8$ 内的整数。 这些值不一定互不相同。

输出格式

输出格式（文件 teleport.out）： 输出一个数，表示 FJ 能达到的 $d_i$ 之和的最小值。 注意该数可能大到无法放入标准 32 位整数中，因此你可能需要使用如 C/C++ 中的 "long long" 之类的大整数数据类型。 另外，你可能需要考虑答案是否一定是整数……

3
-5 -7
-3 10
-2 7

10

提示

在该例中，取 $y = 8$ 时，FJ 可以得到 $d_1 = 2$，$d_2 = 5$，$d_3 = 3$。 注意 $y$ 取在区间 $[7,10]$ 内的任意值也都会得到最优解。 题目来源：Brian Dean

标签: USACO|2018|Silver

来源

USACO|2018|Silver