← 返回题目列表

AtCoder · s8pc_6_b

B. AtCoder 市场

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

最高分数:300 积分

问题陈述

AtCoder Market 是一家超市,包括 1 \ 000 \ 000 \ 000 正方形,从左到右像直线一样连接。让“方 i“ i- 最左边的方块。换句话说,正方形 i 和正方形 i+1 连接所有整数 i \ (1 \leq i \leq 999 \ 999 \ 999).

有一天, N 买家来到AtCoder Market购物。 i第一个买家想要购买两件商品:一件是正方形的 A_i,另一个在正方形中 B_i.

AtCoder Market 的所有者 square1001 将安装一个 入口 和一个 退出.
入口和出口可以安装在任意广场,入口和出口可以放置在同一广场。

然后, i第买家将通过以下方式进行购物:

  • 从入口开始,然后参观广场 A_i, B_i,并在出口处瞄准。他们将沿着最短路线移动。

对于所有买家来说,这完全需要 1 秒移动到相邻的方块。

业主最优选择出入口地点时,最少购物时长之和是多少?

约束

  • 1 \leq N \leq 30
  • 1 \leq A_i < B_i \leq 1 \ 000 \ 000 \ 000

子任务/评分

这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。

  1. (195分):1 \leq A_i < B_i \leq 100。另外,入口和出口都是方形的 1, 2, 3, ..., 100,在最优解中。
  2. (105分):没有额外的限制。

输入

输入将从标准输入给出,格式如下。

N
A_1 B_1
A_2 B_2
 :  :
A_N B_N

输出

在一行中打印购物持续时间的最小总和(以秒为单位)。

注意

在此约束下,答案可能不包含在 32位整数。
使用 64- 位整数,例如在C/C++中,我们可以使用 long long 类型,而不是 int.


示例输入 1

3
5 7
2 6
8 10

示例输出 1

18

考虑在广场安装入口 5,然后在广场退出 7。每位买家的行动如下:

  • 买家编号1:方形 5 -> 6 -> 7
  • 买家编号2:方格 5 -> 4 -> 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
  • 买家编号3:方格 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7

(粗体字表示买家已拿货)

买家 1, 2, 3 将使用 2, 8, 8 秒,因此总购物时间将为 18 秒。
没有办法让总购物时间短于 18 秒。


示例输入 2

5
1 71
43 64
13 35
14 54
79 85

示例输出 2

334

square1001在广场安装入口时 14 并在广场退出 64,总购物时间将为 334 秒,并且是最小值。


示例输入 3

11
15004200 341668840
277786703 825590503
85505967 410375631
797368845 930277710
90107929 763195990
104844373 888031128
338351523 715240891
458782074 493862093
189601059 534714600
299073643 971113974
98291394 443377420

示例输出 3

8494550716

square1001在广场安装入口时 189 \ 601 \ 059 并在广场退出 715 \ 240 \ 891,总购物时间将为 8 \ 494 \ 550 \ 716 秒,并且是最小值。