M. *【贪心】买一送一

    传统题 1000ms 128MiB

*【贪心】买一送一

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

干草有买一送一的活动,每买一捆 AA 干草,就可以免费获赠一捆 BB 干草,赠送的 BB 干草尺寸要满足小于购买 AA 干草尺寸 。

给出 N 捆高质量 AA 干草,每捆尺寸为 aia_i

给出 M 捆次品 BB 干草,每捆尺寸为 bib_i

求最多可以买到多少捆干草。

可以单独买高质量的 AA 干草而没有获赠免费的次品 BB 干草;但不能单独买次品 BB 干草。

【输入格式】

第1行两个整数:N M(1N,M104)N \ M(1 \le N,M \le 10^4)

下来 NN 个整数 aia_i

下来 MM 个整数 bib_i

1ai,bi1061 \le a_i,b_i \le 10^6

【输出格式】

一行一个整数,表示可以买到干草的最大捆数。

【样例输入】

3 4
6 1 3
1 5 3 4

【样例输出】

5

【提示】

共有3捆高质量的干草,尺寸分别是6,1,和3; 共有4捆次品干草,尺寸分别是1,5,3,和4。

显然,可以买到所有高质量的干草。当买尺寸为6的高质量干草时,可以获赠尺寸为3的次品。

当买尺寸为3的高质量干草时,可以获赠尺寸为1的次品。

然而,当买质量为1的高质量干草时,无论如何,都不可能再获赠次品干草。

所以答案就是3+2=5。

入门8.9-8.11(栈+贪心+堆)

未参加
状态
已结束
规则
XCPC
题目
41
开始于
2024-8-1 0:00
结束于
2024-8-15 4:00
持续时间
340 小时
主持人
参赛人数
20