分数: 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