AT_agc069_a [AGC069A] Schedule Optimization

题目描述

高桥君打算举办一个为期 $10^9$ 天的淘汰制比赛。
参赛选手共有 $2^N$ 人，分别称为选手 $1$、$\ldots$、选手 $2^N$。选手 $i$ 计划在第 $l_i$ 天到第 $r_i$ 天之间的 $r_i-l_i+1$ 天内参赛。

首先，介绍比赛的流程。对于所有满足 $1\leq i\leq N,\ 1\leq j\leq 2^{N-i}$ 的整数对 $(i,j)$，共有 $2^N-1$ 种，这些与比赛期间的每场比赛一一对应。与 $(i,j)$ 对应的比赛由以下两位选手进行对决，决出胜者和败者：

• 当 $i=1$ 时，由选手 $2j-1$ 与选手 $2j$ 对战；
• 当 $i\geq 2$ 时，由与 $(i-1,2j-1)$ 对应比赛的胜者和与 $(i-1,2j)$ 对应比赛的胜者对战。

每场比赛只要决定对战的两位选手所需的所有前置比赛都已完成，且这两位选手都在比赛期间内，即可立即进行。特别地，同一位选手在同一天可以参加多场比赛。
与 $(N,1)$ 对应的比赛称为决赛，完成这场比赛即为本次比赛的目标。

为了顺利完成决赛，高桥君可以采取以下措施：

• 指示裁判，随意决定每场比赛的胜者；
• 向各选手支付报酬，调整他们的参赛日程。如果让选手 $i$ 在第 $l'_i$ 天到第 $r'_i$ 天参赛，则需支付 $|l_i-l'_i|+|r_i-r'_i|$ 日元。这里，$l'_i,\ r'_i$ 是满足 $1\leq l'_i\leq r'_i\leq 10^9$ 的整数。

请你求出高桥君为调整选手日程所需支付的最小总金额。

输入格式

输入以如下格式从标准输入读入。

$N$
$l_1$ $r_1$
$\vdots$
$l_{2^N}$ $r_{2^N}$

输出格式

设最小所需支付金额为 $X$ 日元。请输出 $X$。

输入输出样例 #1

输入 #1

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

输出 #1

1

输入输出样例 #2

输入 #2

1
1 1
1000000000 1000000000

输出 #2

999999999

输入输出样例 #3

输入 #3

4
158260522 877914575
24979445 602436426
623690081 861648772
433933447 476190629
211047202 262703497
628894325 971407775
731963982 822804784
430302156 450968417
161735902 982631932
880895728 923078537
189330739 707723857
802329211 910286918
303238506 404539679
317063340 492686568
125660016 773361868
650287940 839296263

输出 #3

1088492036

说明/提示

限制条件

• $1\leq N\leq 18$
• $1\leq l_i\leq r_i\leq 10^9$
• 输入均为整数

样例解释 1

向选手 $4$ 支付 $1$ 日元，将其日程调整为 $(l'_4,r'_4)=(2,3)$，其他选手日程不变。这样，可以按如下方式完成决赛：

1. 第 $1$ 天进行 $(1,1)$ 对应的比赛（选手 $1$ 对选手 $2$），让选手 $2$ 获胜。
2. 第 $3$ 天进行 $(1,2)$ 对应的比赛（选手 $3$ 对选手 $4$），让选手 $3$ 获胜。
3. 第 $3$ 天进行 $(2,1)$ 对应的比赛（选手 $2$ 对选手 $3$），让选手 $3$ 获胜。
4. 第 $3$ 天进行 $(1,4)$ 对应的比赛（选手 $7$ 对选手 $8$），让选手 $8$ 获胜。
5. 第 $4$ 天进行 $(1,3)$ 对应的比赛（选手 $5$ 对选手 $6$），让选手 $5$ 获胜。
6. 第 $4$ 天进行 $(2,2)$ 对应的比赛（选手 $5$ 对选手 $8$），让选手 $8$ 获胜。
7. 第 $4$ 天进行 $(3,1)$ 对应的比赛（选手 $3$ 对选手 $8$），让选手 $8$ 获胜。

而如果支付金额不足 $1$ 日元，则无法完成决赛。因此，期望输出为 $1$。

由 ChatGPT 4.1 翻译