← 返回题目列表

AtCoder · joi2019ho_d

D. 硬币收集

中文机器翻译题面 查看原题

配点: 100 点

JOI先生的收藏室里有一张非常大的桌子,上面有很多值钱的硬币。为了清理办公桌,JOI 先生决定整理并排列他的硬币。

桌子是 它是一个 2\,000\,000\,001 \times 2\,000\,000\,001 的正方形。从左到右,各列是 -1\,000\,000\,000 减去 1\,000\,000\,000 。 它们的编号最大为 -1\,000\,000\,000 减去 1\,000\,000\,000 。列号是 x,行号是 y ( 让我们将其表示为x, y)。

硬币是 2N 目前可用,i 番目 (1 \leqq i \leqq 2N)硬币是正方形(X_i, Y_i)。 JOI先生的目标是1 \leqq x \leqq N 和 1 \leqq y \leqq 2 满足 (x, y) 每个 2N 方格内放置一枚硬币。 1 要一一放置。为了避免损坏硬币, 1 您只能选择一枚硬币并将其移动到与放置它的方格相邻的方格之一。在此过程中,同一个方格上可能会放置多个硬币。 JOI先生希望通过尽可能少的操作来实现他的目标。

给定硬币数量和硬币当前放置的方格,编写一个程序,找出实现目标所需的最少操作数。


入力

输入是按以下格式从标准输入给出的。

N
X_1 Y_1
\vdots
X_{2N} Y_{2N}

出力

将实现目标所需的最少操作数写入标准输出。 1 请以行的形式输出。


制約

  • 1 \leqq N \leqq 100\,000.
  • -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq 2N).
  • -1\,000\,000\,000 \leqq Y_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq 2N).

小課題

  1. (8 点) N \leqq 10.
  2. (29 点) N \leqq 1\,000.
  3. (63 点)没有额外的限制。

入力例 1

3
0 0
0 4
4 0
2 1
2 5
-1 1

出力例 1

15

在此输入示例中,6 硬币的放置方式如下图所示。目标是在粗体框指示的位置收集硬币。

例如,如果您按如下方式移动硬币, 您只需15 操作即可实现您的目标:

  • 1 第枚硬币:( 由于无法通过少于0, 0) → (1, 0) → (1, 1) → (1, 2)
  • 2 第枚硬币:( 由于无法通过少于0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2)
  • 3 第枚硬币:( 由于无法通过少于4, 0) → (4, 1) → (3, 1)
  • 5 第枚硬币:( 由于无法通过少于2, 5) → (2, 4) → (2, 3) → (2, 2)
  • 6 第枚硬币:( 由于无法通过少于-1, 1) → (0, 1) → (1, 1)

14 次操作来实现目标, 输出15 。 你只需要砍掉


入力例 2

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

出力例 2

9

多个硬币可以放置在同一个方块上。


入力例 3

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

出力例 3

8000000029