AT_awc0002_d.鍵と宝箱

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

经过漫长的冒险,Takahashi 来到了一处遗迹,这里有 NN 个宝箱。

每个宝箱 ii(1≤i≤N1 \leq i \leq N)都有一个强度为 CiC_i 的锁。强度越大表示锁越坚固。所有宝箱的锁强度两两不同。

Takahashi 有 MM 把钥匙。每把钥匙 jj(1≤j≤M1 \leq j \leq M)有一个开锁能力 RjR_j。钥匙 jj 只有在其开锁能力不小于锁的强度时(即 Ci≤RjC_i \leq R_j),才能打开宝箱 ii。不同的钥匙可能有相同的开锁能力。

Takahashi 可以选择一些(也可以不选,甚至 00 个)宝箱开启,并且每个被选中的宝箱都要分配恰好一把钥匙来开启。但是,同一把钥匙不能被分配给两个或以上的宝箱。并且分配给每个宝箱的钥匙,必须能够打开该宝箱(即 Ci≤RjC_i \leq R_j)。可以留下部分钥匙未用,也可以有部分宝箱未开。

请你求出 Takahashi 最多能打开多少个宝箱。

输入格式

NN MM
C1C_1 C2C_2 …\ldots CNC_N
R1R_1 R2R_2 …\ldots RMR_M

  • 第一行包含两个整数 NN 表示宝箱数量和 MM 表示钥匙数量,以空格分隔。
  • 第二行包含 C1,C2,…,CNC_1, C_2, \ldots, C_N,表示每个宝箱的锁强度,以空格分隔。
  • 第三行包含 R1,R2,…,RMR_1, R_2, \ldots, R_M,表示每把钥匙的开锁能力,以空格分隔。

输出格式

输出一个整数,表示 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×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Ci≤1091 \leq C_i \leq 10^9(1≤i≤N1 \leq i \leq N)
  • 1≤Rj≤1091 \leq R_j \leq 10^9(1≤j≤M1 \leq j \leq M)
  • Ci≠CkC_i \neq C_k(i≠ki \neq k)(所有锁强度互不相同)
  • 所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页