← 返回题目列表

AtCoder · awc0048_b

B. 走廊里的脚步声

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

分数: 333 分

问题陈述

高桥正试图穿过一条长长的走廊, N 瓷砖排列成一排。瓷砖从左到右编号为 Tile 1,瓷砖 2, \ldots,瓷砖 N.

每块瓷砖都布满了灰尘。最初,瓷砖 i 有厚厚的灰尘 H_i。当高桥踩到瓷砖时 i,该瓷砖上的灰尘厚度变为 \max(0,\; H_i - D_i),其中 D_i 是为 Tile 定义的非负整数 i。高桥未踩过的瓷砖上的灰尘厚度保持初始厚度不变 H_i.

高桥从 Tile 开始 1和瓷砖 N 是目标。高桥总是只向右移动。具体来说,当他目前在 Tile 上时 j,他可以选择 Tile j+1 或平铺 j+2 作为他的下一个目的地。然而,他无法超越瓷砖 N (他可以移动到方块 j+1 仅当 j+1 \leq N,然后平铺 j+2 仅当 j+2 \leq N)。高桥一到达瓷砖就踩到了它。他还踩过瓷砖 1,起点。高桥到达瓷砖后结束动作 N.

由于上述移动规则,Tile 1 和瓷砖 N 总是被踩到。此外,由于高桥总是向右移动,因此他不会多次踩到同一块瓷砖。

高桥走过走廊后,青木检查了走廊并数了数 带有脚印的瓷砖。瓷砖上留下足迹 i 如果瓷砖上的灰尘厚度 i 高桥移动后严格小于初始厚度 H_i.

  • 如果高桥没有踩到瓷砖 i,灰尘厚度保持不变 H_i,因此没有留下足迹。
  • 如果高桥踩到瓷砖 i,灰尘厚度变为 \max(0,\; H_i - D_i)。这严格小于 H_i 当且仅当 H_i > 0 和 D_i > 0。因此,如果 H_i = 0 or D_i = 0,即使踩到瓷砖也不会留下足迹。

Takahashi 希望最大限度地减少带有足迹的瓷砖数量。求当高桥沿着最优路径移动时,有脚印的瓷砖的最少数量。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • 所有输入值均为整数。

输入

N
H_1 H_2 \cdots H_N
D_1 D_2 \cdots D_N
  • 第一行包含一个整数 N,瓷砖数量。
  • 第二行包含 N 整数 H_1, H_2, \ldots, H_N 以空格分隔,代表每块瓷砖的初始灰尘厚度。
  • 第三行包含 N 整数 D_1, D_2, \ldots, D_N 以空格分隔,代表每块瓷砖踩踏时的降尘上限。

输出

在一行中打印高桥最佳移动时带有脚印的最小瓷砖数量。


示例输入 1

5
3 0 5 2 4
1 1 1 1 1

示例输出 1

3

示例输入 2

8
5 0 3 0 7 0 2 4
2 3 0 1 1 5 1 3

示例输出 2

2

示例输入 3

15
1 1 0 1 0 1 1 0 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

示例输出 3

5