web analytics

JZOJ.4825 舞会配对 解题报告

Description
在舞会上有N个男孩和N个女孩,每个人都量过了自己的身高。每个男孩只跟女孩跳舞,并且女孩也只跟男孩跳舞。每个人最多只有一个舞伴。男孩或者想和比自己高的女孩跳舞,或者想和比自己低的女孩跳舞,同样的,女孩也是或者想和比自己高的男孩跳舞,或者想和比自己低的男孩跳舞。
你能决定最多有多少对能在一起跳舞吗?
Input
第一行是一个正整数N(1<=N<=100,000),表示男女的人数。
第二行包括N个绝对值在1500到2500的整数,每个整数的绝对值表示每个男孩的身高。如果是一个正整数,表示这个男的喜欢和比他高的女孩跳舞,如果是负整数,就表示这个男的喜欢和比他低的女孩跳舞。
第三行包括N个整数,每个整数的绝对值表示相应女孩的身高。同样的,如果是正整数的话,表示这个女孩喜欢和比她高的男孩跳舞,如果是负整数的话,表示这个女孩喜欢和比她低的男孩跳舞。
Output
只有一行一个整数,表示最多的可以搭配的对数。
Sample Input
输入1:
1
-1800
1800
输入2:
1
1700
-1800
输入3:
2
-1800 -2200
1900 1700
Sample Output
输出1:
0
输出2:
1
输出3:
2
Data Constraint
对于50%的数据满足:N<=5000
对于100%的数据满足:1<=N<=100,000

分析:

这道题通过观察我们发现.这道题其实有4个部分.1是+男生 2是-男生 3是+女生 4是-女生. 而这4部分又有 +男生和-女生在一起.-男生和+女生在一起.这里不会出现+男生和+女生在一起的情况.而我们又保证最优解出现,所以这里可以用到贪心策略来解决这个问题.为什么?

首先我们可以分2组,把4部分组合一下.而我们因为+男生喜欢和比他高的女孩跳舞。而我们在这里可以将4组从小到大排序。+男生与-女生从小到大开始一个一个的取。如果满足条件就同时取出。如果男生要比女生高。那说明这个女生。无论怎么找都找不到别人了。如果她到比她小的男生。那么前面的算出来的对数一定不是最优的。因为这里前面的人又有可能满足不了。这样贪下去。。我们每次保证最大的对数。所以最后算下来就是这样。

这里给出官方题解:

给你 N 对男孩和女孩的身高,让你进行配对,其中某些男孩和比自己高的女孩搭配,另一些 和比自己低的女孩搭配,女孩也是如此,让你求出最大的搭配对数。 贪心。 首先,我们要知道对于喜欢和比自己低的女孩跳舞的男孩,就应该要从喜欢和比自己高的男 孩跳舞且比那个男孩的低的女孩中选择那个最高的女孩。比如说样例 3 中,身高为 2200 的男孩 应该和身高为 1900 的女孩搭配,但如果他和身高为 1700 的女孩搭配,则身高为 1800 的男孩就 不能找到能和自己跳舞的女孩了,那么搭配对数就会减少 1 对,从而该方案也不是最优方案了, 故不可取。 明确了这一点,我们就可以很容易的想到用贪心来解决问题。先将 4 类孩子的身高分开存储 在 a、b、c、d4 个数组中(a 数组存放喜欢和比自己低的女孩跳舞的男孩,a[0]表示个数;b 数 组存放喜欢和比自己高的女孩跳舞的男孩,b[0]表示个数;c 数组存放喜欢和比自己低的男孩 跳舞的女孩,c[0]表示个数;d 数组存放喜欢和比自己高的男孩跳舞的女孩,d[0]表示个数), 再将它们进行排序,然后进行贪心,最后输出答案即可,时间复杂度应该为 O(N*logN)。

Post a Comment

You must be logged in to post a comment.