#P1223. 陪练配对

    ID: 235 传统题 1000ms 512MiB 尝试: 0 已通过: 0难度: 普及+/提高− ← 上一题 下一题 → 随机一题 上传者: 标签 贪心 排序 双指针
显示设置

陪练配对

陪练配对

题目背景

集训队要组织一次“一对一”陪练:每名队员负责一个训练任务,一名队员恰好带一个任务。教练发现,如果队员的能力值和任务的难度相差太大,训练效果就会很差;只有相差不超过某个阈值 DD 的搭配,才算是一次“合适”的配对。教练希望尽可能多的搭配是合适的。

题目描述

集训队有 nn 名队员和 nn 个训练任务。第 ii 名队员的能力值记为 aia_i,第 jj 个任务的难度记为 bjb_j。

现在要把队员和任务一一配对:每名队员恰好负责一个任务,每个任务恰好由一名队员负责。如果队员 ii 与任务 jj 配成一对,并且

∣ai−bj∣≤D,|a_i - b_j| \le D ,

那么就称这一对是合适的。

请你求出:在所有的配对方案中,最多能有多少对是合适的。

输入格式

从标准输入读入数据。

第一行两个整数 n,Dn, D。

第二行 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n,表示每名队员的能力值。

第三行 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n,表示每个任务的难度。

输出格式

输出到标准输出。

一行一个整数,表示最多合适配对的对数。

样例 1 输入

3 1
1 5 9
2 6 8

样例 1 输出

3

样例 1 解释

把能力值 11 的队员配给难度 22 的任务(相差 11),能力值 55 的队员配给难度 66 的任务(相差 11),能力值 99 的队员配给难度 88 的任务(相差 11),三对都合适。

样例 2 输入

2 0
4 7
7 7

样例 2 输出

1

样例 2 解释

两个任务的难度都是 77。能力值为 77 的队员与任意一个任务配对(相差 00)都合适,但能力值为 44 的队员与难度 77 的任务相差 33,不合适。无论怎么配对,最多只有一对合适。

数据范围

测试点编号 n≤n \le 特殊性质
1∼31 \sim 3 2020 无
4∼64 \sim 6 20002000
7∼107 \sim 10 2×1052 \times 10^5

对全部测试数据,保证 1≤n≤2×1051 \le n \le 2 \times 10^5,0≤D≤1090 \le D \le 10^9,1≤ai,bj≤1091 \le a_i, b_j \le 10^9。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据,并将答案输出到标准输出。