匹配问题 - 题目

数轴上有 $n$ 个黑点，坐标为 $a[]$；$n$ 个白点，坐标为 $b[]$（下标均从 $0$ 开始）。同时你有两个参数 $l_a$ 和 $l_b$，满足 $n \geq 2$ 且 $1 \leq l_b < l_a$。注意同一个位置可能有多个点。

你需要找到一个 $0$ 到 $n-1$ 的排列 $p[]$，满足对于所有 $i$，有 $a[i] \leq b[p[i]] \leq a[i] + l_a$。你需要最大化满足 $b[p[i]] \leq a[i] + l_b$ 的下标 $i$ 的个数。数据保证存在一个合法的排列。

第一行，三个正整数 $n$，$l_a$，$l_b$。

接下来一行，$n$ 个正整数，表示 $a[]$。

接下来一行，$n$ 个正整数，表示 $b[]$。

输出一行一个非负整数，表示满足条件的下标个数。

3 5 1
1 2 5
4 6 7

$n=3$，$l_a=5$，$l_b=1$

$a[] = \{1, 2, 5\}$

$b[] = \{4, 6, 7\}$

一种最好的排列是 $p[] = \{0, 2, 1\}$，$b[p[2]] = b[1] = 6$ 和 $a[2] = 5$ 的差不超过 $l_b = 1$，其他均不满足这个条件，答案为 $1$。

$p[] = \{2, 0, 1\}$ 不是合法的排列，因为 $b[2] = 7$ 被 $a[0] = 1$ 匹配，它们的差为 $6$，超过了 $l_a = 5$。

$p[] = \{1, 2, 0\}$ 不是合法的排列，因为 $b[0] = 4$ 被 $a[2] = 5$ 匹配，但不满足 $b[0] \geq a[2]$。

$p[] = \{0, 1, 2\}$ 虽然是合法的排列，但是答案为 $0$，不是最优解。

子任务 1（4 分）：满足 $n \leq 10$。

子任务 2（14 分）：满足 $n \leq 100$。

子任务 3（37 分）：满足 $n \leq 5\,000$。

子任务 4（16 分）：满足 $l_a = 5 \times 10^5$。

子任务 5（29 分）：无特殊限制。

对于所有数据，$2 \leq n \leq 5 \times 10^5$，$1 \leq a[i], b[i] \leq 5 \times 10^5$，$1 \leq l_b \leq l_a \leq 5 \times 10^5$。保证存在一个合法的排列。

QOJ.ac