完美匹配(match)

给定 $n$ 个 $a_i$ 和 $m$ 个 $b_i$，要求满足 $a_i + b_j \ge S$ 且 $|a_i - b_j| \le D$ 的可以配对一次，每一个 $a_i$ 或 $b_i$ 只能配对一次，问最大配对方案。

对于特殊性质 $\text{A}$：满足 $D = 10 ^ 9$。

测试点 1 ~ 2 (20pts)

由于 $n, m \le 10$，所以，我们可以暴力的去 DFS，每次为当前的试卷找一个配对的人，时间复杂度 $\mathcal{O}(m ^n \times n)$。

实现略。

测试点 3 ~ 4 （20pts）

由于 $n, m \le 1000$，我们就可以考虑 $nm$ 的做法。

匹配的问题，不可避免的可以想到去跑二分图匹配，只要我们能把边建出来。

对于建边的过程，我们可以选择 $\mathcal{O}(nm)$ 的去判断是否可以配对，连边。

连完边之后我们就可以直接进行二分图最大匹配。而二分图最大匹配的复杂度理论是 $\mathcal{O}(nm)$，可以通过。

测试点 5 ~ 6 （20pts）

因为 $D \le 10 ^ 9$，因此对于任意的 $a_i, b_j \in [1, 10 ^ 9]$，一定有 $|a_i - b_j| \le D$，所以我们现在只有第一个条件需要看。

第一个条件很简单，就是 $a_i + b_j \ge S$。

我们要选择尽可能多的匹配。

我们可以把这个式子转化一下，那么对于 $b_i$ 来说，就是 $b_i \ge S- a_i$，我们令 $c_i = S - a_i$，那么对于每一个 $b_i$ 只有让 $c_j \le b_i$ 的时候，就可以让这个 $a_j$ 和 $b_i$ 进行配合。

那就很简单了，我们只需要把 $c_i$ 和 $b_i$ 进行升序排序，我们对于每一个 $b_i$ 可以选择最大的 $\le b_i$ 的 $c_i$，这个过程可以利用双指针，或者放一个堆。

时间复杂度 $\mathcal{O}(n \log n)$

测试点 7 ~ 10 (40pts)

实际上对于特殊性质 $A$ 来说，已经给了我们一些提示，那就可以把这个不等式进行转化：

首先是我们还是先以 $b_i$ 为主，那么就可以转化为，$b_j \ge S - a_i$，第二个不等式我们可以把绝对值拆开，左边是 $b_j \ge a_i - D$，右边就是 $b_j \le a_i + D$。

那么对于每一个 $b_j$ 来说，我们能选到的就是区间 $[\max(S - a_i , a_i - D), a_i + D]$。

因此现在的问题就变为了，现在有若干个区间，和若干个点，每一个点只能匹配一个区间，问最大的匹配数量。这是一个很经典的贪心模型，我们直接对于每一个区间按左端点排序，对于每一个 $b_j$ 也按是升序排序，我们遍历每一个 $b_i$，对于每一个 $b_i$ 来说，我们能选择的是覆盖这个点的 $r$ 最小的区间，那么这个过程我们可以直接用一个小根堆维护。

时间复杂度 $\mathcal{O}(n \log n)$