D. 任务匹配

    传统题 1000ms 256MiB

任务匹配

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

题目描述

图灵之星\text{图灵之星}nn 名同学和 mm 个训练任务。

ii 名同学的能力值为 aia_i,第 jj 个训练任务的难度为 bjb_j

一名同学最多只能完成一个任务,一个任务也最多只能由一名同学完成。

如果某名同学的能力值不小于某个任务的难度,那么这名同学就可以完成这个任务。也就是说,当:$$a_i \ge b_j$$时,同学 ii 可以完成任务 jj

现在请你安排同学完成任务,使完成的任务数量尽可能多。

如果有多种安排方案都能完成最多任务,请在这些方案中,使被安排同学的能力值总和尽可能小。

请输出:

  1. 最多可以完成多少个任务;
  2. 在完成任务数量最多的前提下,被安排同学能力值总和的最小值。

输入格式

第一行包含两个整数 n,mn,m,分别表示同学数量和任务数量。

第二行包含 nn 个整数:a1,a2,,ana_1,a_2,\ldots,a_n,表示每名同学的能力值。

第三行包含 mm 个整数:b1,b2,,bmb_1,b_2,\ldots,b_m,表示每个任务的难度。

输出格式

输出一行两个整数,分别表示最多完成的任务数量,以及在最多完成任务数量前提下,被安排同学能力值总和的最小值。

5 4
3 8 5 10 6
4 6 7 2
4 22

样例解释

一种最优安排为:

  • 能力值为 33 的同学完成难度为 22 的任务;
  • 能力值为 88 的同学完成难度为 77 的任务。
  • 能力值为 55 的同学完成难度为 44 的任务;
  • 能力值为 66 的同学完成难度为 66 的任务;

最多可以完成 44 个任务,被安排同学能力值总和为:$$3+5+6+8=22$$可以证明这是最优的情况。

4 3
1 1 1 1
5 6 7
0 0

样例解释

很明显,一个都完成不了。

数据范围与约定

对于所有测试数据,保证:$1 \le n,m \le 2\times 10^5,\quad 1 \le a_i,b_i \le 10^9$

图灵周赛 Round 52(二场)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-6-13 9:00
结束于
2026-6-14 18:00
持续时间
2 小时
主持人
参赛人数
21