← 返回题目列表

AtCoder · agc049_c

C. 机器人

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

分数: 800 点

问题陈述

数轴上有机器人。 具体来说,对于每个 i=0,1,2,\cdots,10^{100},只有一个机器人叫Robot i 位于坐标处 i.

我们有很多球。 每个球上都写有一个正整数。 整数序列 A 和 B,每个长度 N,描述这些球。 具体来说,对于每个 i (1 \leq i \leq N),有 B_i 球与 上面写着 A_i 。

现在,Snuke 将执行以下操作序列:

  • 步骤 1:选择零个或多个球,并将这些球上写的整数替换为 正整数 他的选择 1 和 10^{100} (含)。 (新的整数可以彼此独立地选择。)

  • 第二步:按照自己选择的任意顺序将球一粒一粒地吃掉。每次他吃球时,他应该做以下事情:

    • 让 v 是他刚刚吃掉的球上写的整数。如果机器人 v 存在,移动它,使其坐标减少 1。在这里,如果目的地有另一个机器人,则该机器人(不是机器人 v)将被销毁。

Snuke 想要吃掉所有的球而不摧毁机器人 0。 找出 Snuke 在第 1 步中必须选择的最小球数才能实现其目标。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_1 < A_2 < \ldots < A_N \leq 10^9
  • 1 \leq B_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

输出

打印答案。


示例输入 1

3
1 2 3
1 2 1

示例输出 1

1

我们可以通过选择一个球来实现目标 2 ,重写 3 就可以了,然后按以下顺序吃球:

  • 吃球 上面写着 2 ,移动机器人 2 来自坐标 2 协调 1 并摧毁机器人 上面写着 1.

  • 吃球 上面写着 3 ,移动机器人 3 来自坐标 3 协调 2.

  • 吃球 上面写着 3 ,移动机器人 3 来自坐标 2 协调 1 并摧毁机器人 上面写着 2.

  • 吃球 上面写着 1 。机器人 1 已经被摧毁,所以什么也没有发生。


示例输入 2

4
1 3 5 7
3 1 4 1

示例输出 2

0