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$ 位置。

无

无

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