任务分配问题

题目描述

今天某公司有 $M$ 个任务需要完成。

每个任务都有相应的难度级别和完成任务所需时间。

第 $i$ 个任务的难度级别为 $y_i$，完成任务所需时间为 $x_i$ 分钟。

如果公司完成此任务，他们将获得 $(500 \times x_i + 2 \times y_i)$ 美元收入。

该公司有 $N$ 台机器，每台机器都有最长工作时间和级别。

如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。

如果任务难度级别超过机器的级别，则机器无法完成此任务。

每台机器一天内只能完成一项任务。

每个任务只能由一台机器完成。

请为他们设计一个任务分配方案，使得该公司能够最大化他们今天可以完成的任务数量。

如果有多种解决方案，他们希望选取赚取利润最高的那种。

输入格式

输入包含几个测试用例。

对于每个测试用例，第一行包含两个整数 $N$ 和 $M$，分别代表机器数量和任务数量。

接下来 $N$ 行，每行包含两个整数 $x_i, y_i$，分别代表机器最长工作时间和机器级别。

再接下来 $M$ 行，每行包含两个整数 $x_i, y_i$，分别代表完成任务所需时间和任务难度级别。

输出格式

对于每个测试用例，输出两个整数，代表公司今天可以完成的最大任务数以及他们将获得的收入。

输入输出样例 #1

输入样例

1 2
100 3
100 2
100 1

输出样例

1 50004

输入输出样例 #2

输入样例

2 3
100 3
200 1
50 2
100 1
150 2

输出样例

2 150012

限制条件

• $1 \le N, M \le 100000$
• $0 < x_i < 1440$
• $0 \le y_i \le 100$

样例解释 #1

有 1 台机器：最长工作时间 100，级别 3 有 2 个任务：

1. 任务1：所需时间 100，级别 2
2. 任务2：所需时间 100，级别 1

机器可以完成这两个任务（时间不超过 100，级别不超过 3），但只能完成一个任务。

收入计算：

• 任务1：$500 \times 100 + 2 \times 2 = 50000 + 4 = 50004$
• 任务2：$500 \times 100 + 2 \times 1 = 50000 + 2 = 50002$

为了最大化收入，选择收入更高的任务1，收入为 50004。 因此输出 1 50004。

问题分析

这是一个贪心+匹配问题：

1. 约束条件：机器 $(x_m, y_m)$ 可以完成任务 $(x_t, y_t)$ 当且仅当 $x_m \ge x_t$ 且 $y_m \ge y_t$
2. 目标：最大化完成任务数量，在此基础上最大化总收入
3. 收入公式：$500 \times x_t + 2 \times y_t$

观察收入公式：

• $x_t$ 的系数是 500，$y_t$ 的系数是 2
• 由于 $x_t < 1440$，$y_t \le 100$，$500 \times 1440 = 720000$，$2 \times 100 = 200$
• 所以 $x_t$ 对收入的影响远大于 $y_t$

因此，要最大化总收入，应该优先完成 $x_t$ 大的任务（因为 $x_t$ 对收入的贡献远大于 $y_t$）。

贪心策略

1. 将任务和机器都按照 $x$ 从大到小排序，如果 $x$ 相同则按照 $y$ 从大到小排序
2. 遍历每个任务，找到所有 $x$ 不小于当前任务 $x$ 的机器
3. 从这些机器中选择 $y$ 不小于任务 $y$ 且 $y$ 最小的机器（为了尽量保留 $y$ 大的机器给后面的任务）
4. 使用多重集合或树状数组来维护可用机器的 $y$ 值

具体步骤：

• 对机器和任务按 $x$ 降序排序
• 使用一个指针遍历机器
• 对于每个任务，将所有 $x$ 不小于该任务 $x$ 的机器加入集合（按 $y$ 组织）
• 在集合中寻找 $y$ 不小于任务 $y$ 的最小 $y$ 值的机器
• 如果找到，完成任务计数并累加收入，同时从集合中移除该机器

时间复杂度：$O((N+M) \log N)$，可以使用平衡树或树状数组实现。