web analytics

noip 模拟赛 匹配 //贪婪策略

匹配(match.pas/match.c/match.cpp)

[题目描述]

到了新的学期,Mcx痛苦的发现通用技术课居然是有实验课的,这样的话他就不得不放弃写作业的想法而去做一件类似于搭积木的事情。一次实验课上,他发现所给的材料有许许多多的长积木,其中黄色的有n条,第i条的长度为Ai;蓝色的有m条,第j条的长度为Bj。于是他想:这些积木可以组成多少对导轨呢?每对导轨由一条黄色积木和一条蓝色积木组成,每条积木只能用一次。为了美观,当且仅当Ai– x <= Bj <= Ai + y的时候,两条积木才能组成一对导轨。x,y为给定的非负整数。

[题目输入]

第一行四个数n,m,x,y,具体含义见题目描述。

第二行n个数,第i个数表示第i条黄色积木的长度,每两个数之间有一个空格。

第三行m个数,第i个数表示第i条蓝色积木的长度,每两个数之间有一个空格。

[题目输出]

仅一行一个非负整数,表示所能组成的导轨对数的最大值。

[样例输入]

5 3 0 0

1 2 3 3 4

1 3 5

[样例输出]

2

[样例解释]

样例中x,y均为0,故只有当Ai=Bj的时候才能组成一对导轨。

方案为第一条黄色积木和第一条蓝色积木一组,第二条蓝色积木和第三或第四条黄色积木一组。

[数据范围]

50%的数据满足1<= n , m <= 1000

100%的数据满足1<= n , m <= 100000

100%的数据满足0<= x , y , Ai , Bi <= 10^9

100%的数据满足,AiBi一定为升序排列。

分析:

拿到这道题,其实首先可以想到如果数据小,用匈牙利算法是可以跑下来的。但是很不巧,我不会。考虑别的做法,发现如果我们瞎基本贪心。好像可以做诶。接下来就是如果瞎基本贪心?很显然我们在这里如果每次都选择符合要求区间内最小值。由于序列成单调递增。那么我们可以保证,每次最先让前面的匹配。

假设Ai<=Aj 还有Bi

放出代码:这里要注意边界判断与及时对循环终止。

Post a Comment

You must be logged in to post a comment.