首页 > 试题广场 >

约会匹配

[编程题]约会匹配
  • 热度指数：397 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
网易公司在七夕节前后内部都会组织相亲活动，但是由于人数众多，为了提高效率，主办方设计了一个系统。所有男生先登录系统，观看女生资料，然后在系统中登记他们自己有初步意向的女生，可以登记多个。反之女生也可以在系统中登记多个有初步意向的男生。如果某个女生和某个男生同时互相都有意向，则认定为匹配。

最终系统会取出所有系统互相都初步匹配成功的男生女生，尽量地促成他们的真实约会，约会形式是互相匹配的一男与一女单独约会，但是被选中的男生女生最多只能约会一次。问该系统最多能够促成多少次约会，让尽可能多的男生女生得到约会机会。

输入描述:
第一行输入为所有男生的id序列， 0< id数量 < 10000，用空格切分
第二行输入为所有女生的id序列， 0< id数量 < 10000，用空格切分
第三行为有已经有多少个匹配数n
下面有n行，每一行为一个已经初步互相匹配的男生女生id对，为两个数字，第一个为男生id，第二个为女生id，用空格区分


输出描述:
一个整数，最多能够促成多少次约会
示例1

输入

0 1 2
3 4 5
6
0 4
0 3
1 3
1 4
2 5
2 4

输出

3

说明

该case存在有多个互相匹配的情况，但是经过分析，0-3, 1-4, 2-5这种约会安排方法，保证尽量多的约会，同时每人只约会最多一次。
算法知识视频讲解
开通博客

暂无题解

问题信息

iOS工程师 安卓工程师 运维工程师 算法工程师 网易 游戏研发工程师 2021 Java工程师
上传者：小小
难度：
7条回答 2981浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号