Codechef-CHEFPRAD(找事件点+贪心)

题意:

定义一个函数maxMatching(A,B,y),其输入包含两个整数数组 A 和 B 以及一个整数 y,返回一个整数。

记数组 A 的大小为 N,数组 B 的大小为 M。考虑一个由 {a1, a2, ... , aN } 和 {b1, b2, ... , bM}

两个顶点集构成的二分图。节点 ai 和 bj 之间存在边相连当且仅当 abs(Ai - Bj ) <= y。函数maxMatching(A,B,y)便返回这个这个二分图的最大匹配。

现在给你两个整数数组 C 和 D 和一个整数 e,请你输出下面这段程序的运行结果:

------------------------------------

ans = maxMatching(C, D, e)

FOR x = -2e9..2e9

FOR i = 1..N

F[i] = C[i] + x

ans = max(ans, maxMatching(F, D, e))

output ans

------------------------------------

输入第一行包含一个整数 T,表示测试数据组数。

对于每组测试数据第一行包含三个整数 N, M, e,分别表示数组 C 的大小,数组 D 的大小和 e。

第二行包含 N 个空格隔开的整数表示数组 C。

第三行包含 M 个空格隔开的整数表示数组 M。

对于每组测试数据,输出程序的运行结果ans,每组测试数据一行。

1 <= T <= 10, 1 <= N, M <= 250, 1 <= Ci, Di, e <= 1e9。

分析:

先不考虑x,思考如何快速求出最大匹配

可以先对两边从小到大排序,那么考虑左边的每个点,向右连出的边肯定覆盖右边的一个区间,并且这个覆盖区间两端点都是非递减的

所以可以采用贪心的方法,考察每个左边点,尽量取右边能取到的最上面的那个点,这样可以O(n)求出最大匹配

现在还有x的问题

注意到并不是每个x都会改变图的结构

我们只考察那些改变图结构的x,即某个x让左边的某个点覆盖区间变了

我们考虑点对(i,j),找到最小的x和最大的x使得左边点i和右边点j恰好相连

那么对于每个点对,就有2个x需要考虑

总共就有2*n*m个x需要考虑(这些x就是事件点)

我们对这每个事件点对应的图进行贪心求最大匹配

时间复杂度O(n^2*m)

原文地址:https://www.cnblogs.com/wmrv587/p/7055281.html