← 返回题目列表

AtCoder · awc0020_e

E. 将书籍放在书架上

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

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