#1744. 匹配问题

    ID: 1744 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1088来源:qoj.ac数据:公开样例单调栈

匹配问题

匹配问题

题目描述

标题: 匹配问题 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

数轴上有 n 个黑点,坐标为 a[];n 个白点,坐标为 b[](下标均从 0 开始)。同时你有两个参数 la 和 lb,满足 n≥2 且 1≤lb<la。注意同一个位置可能有多个点。

你需要找到一个 0 到 n−1 的排列 p[],满足对于所有 i,有 a[i]≤b[p[i]]≤a[i]+la。你需要最大化满足 b[p[i]]≤a[i]+lb 的下标 i 的个数。数据保证存在一个合法的排列。

输入格式

第一行,三个正整数 n,la,lb。

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

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

输出格式

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

样例数据

样例输入

3 5 1
1 2 5
4 6 7

样例输出

1

样例解释

n=3,la=5,lb=1

a[]={1,2,5}

b[]={4,6,7}

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

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

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

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

子任务

子任务 1(4 分):满足 n≤10。

子任务 2(14 分):满足 n≤100。

子任务 3(37 分):满足 n≤5000。

子任务 4(16 分):满足 la=5×105。

子任务 5(29 分):无特殊限制。

对于所有数据,2≤n≤5×105,1≤a[i],b[i]≤5×105,1≤lb≤la≤5×105。保证存在一个合法的排列。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 5 1
1 2 5
4 6 7
1