AT_awc0002_d.鍵と宝箱
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
经过漫长的冒险,Takahashi 来到了一处遗迹,这里有 N 个宝箱。
每个宝箱 i(1≤i≤N)都有一个强度为 Ci 的锁。强度越大表示锁越坚固。所有宝箱的锁强度两两不同。
Takahashi 有 M 把钥匙。每把钥匙 j(1≤j≤M)有一个开锁能力 Rj。钥匙 j 只有在其开锁能力不小于锁的强度时(即 Ci≤Rj),才能打开宝箱 i。不同的钥匙可能有相同的开锁能力。
Takahashi 可以选择一些(也可以不选,甚至 0 个)宝箱开启,并且每个被选中的宝箱都要分配恰好一把钥匙来开启。但是,同一把钥匙不能被分配给两个或以上的宝箱。并且分配给每个宝箱的钥匙,必须能够打开该宝箱(即 Ci≤Rj)。可以留下部分钥匙未用,也可以有部分宝箱未开。
请你求出 Takahashi 最多能打开多少个宝箱。
输入格式
N M
C1 C2 … CN
R1 R2 … RM
- 第一行包含两个整数 N 表示宝箱数量和 M 表示钥匙数量,以空格分隔。
- 第二行包含 C1,C2,…,CN,表示每个宝箱的锁强度,以空格分隔。
- 第三行包含 R1,R2,…,RM,表示每把钥匙的开锁能力,以空格分隔。
输出格式
输出一个整数,表示 Takahashi 最多能打开多少个宝箱。
输入输出样例
输入#1
3 3 10 20 30 15 25 35
输出#1
3
输入#2
5 3 100 200 300 400 500 150 250 450
输出#2
3
输入#3
7 10 50 120 80 200 350 500 1000 40 60 100 100 150 200 300 400 600 1500
输出#3
7
说明/提示
数据范围
- 1≤N≤2×105
- 1≤M≤2×105
- 1≤Ci≤109(1≤i≤N)
- 1≤Rj≤109(1≤j≤M)
- Ci=Ck(i=k)(所有锁强度互不相同)
- 所有输入值均为整数。
由 ChatGPT 5 翻译
输入解题思路,AI测评打分。不知道怎么写?