分数: 433 分
问题陈述
高桥,担任图书管理员,被分配了上架的任务 N 书放在书架上。
书架上有 M 空格排列成行,从左到右编号为空格 1,空格 2, \ldots,空格 M。每个空间 j 有一个整数值 C_j 代表其“承重能力”,每个空间最多可容纳 1 书。
书籍编号为 1 to N,并预订 i 有一个整数值 W_i 代表其“重量”。
Takahashi 在订单簿中一次确定每本书的位置 1,书 2, \ldots,书 N,使用以下过程:
- 在尚未放置书籍的空间中,将那些承重能力至少为书籍重量的空间视为候选空间(即, C_j \geq W_i).
- 如果至少有一个候选,则将书放在编号最小的候选空间上。放置书籍的空间已被占用,无法再选择放置后续书籍。
- 如果没有候选人,就放弃搁置那本书。一本被放弃的书不会被放在书架上,也不会被重新考虑。
考虑所有书籍的放置后,确定成功放置到书架上的书籍数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
- 所有输入均为整数
输入
N M W_1 W_2 \ldots W_N C_1 C_2 \ldots C_M
- 第一行包含 N,书籍数量,以及 M,书架上的空格数,以空格分隔。
- 第二行包含每本书的重量 W_1, W_2, \ldots, W_N,用空格分隔。
- 第三行包含每个空间的重量容量 C_1, C_2, \ldots, C_M,用空格分隔。
输出
在一行上打印成功放置在书架上的书籍数量。
样本输入 1
4 5 3 5 2 7 4 6 3 8 2
示例输出 1
4
示例输入 2
6 5 5 3 8 2 10 1 7 4 9 3 6
示例输出 2
5
示例输入 3
10 8 5 1 9 3 7 6 2 4 8 10 6 3 10 5 8 2 7 4
示例输出 3
8