#941. 赛马
赛马
题目描述
有 匹白马,编号为 ~ 。每匹马有一个马力值,编号为 的白马的马力值为 。
有 匹黑马,这些黑马围成一圈,按顺时针依次编号为 ~ 。 号黑马的顺时针方向下一匹马为 号黑马。每匹马有一个马力值,编号为 的黑马的马力值为 。
现在 和 要进行跑马比赛。比赛共分 场,每场比赛双方各派出一匹马进行角逐,马力值大的一方将获胜。每匹马仅允许上场一次。
首先为他的每匹马分配了一个期望对手。编号为 的白马期望对手是编号为 的黑马。
不过可能有多匹白马分配了同一匹黑马对手。这不符合比赛规则。每匹马只能上场一次。于是 需要修改他的分配策略。
经过调整, 作出了如下策略:
选择一匹尚未分配对手的白马,假设其编号为 ,让它去和期望对手 比赛;但如果 已经匹配了对手,则 会顺时针尝试匹配下一匹黑马;如果下一匹黑马尚未分配对手,则 与其匹配成功,否则 会继续顺时针尝试匹配下一匹黑马,直到匹配成功。
不断重复以上匹配方式,直到所有马匹配成功。
问: 如何为自己的白马分配对手,可以使得自己获胜场次最多?
你只需要输出 最多能获胜多少场。
输入格式
第一行:包含一个整数 。
第二行:包含 个整数 ;
第三行:包含 个整数 ;
第四行:包含 个整数 ;
数据保证不管黑马白马都不存在相同的马力值。
输出格式
一个整数,表示答案。
样例 1 输入
3
2 3 3
4 1 10
2 7 3
样例 1 输出
2
样例 2 输入
4
3 1 3 3
5 8 7 10
4 1 2 6
样例 2 输出
1
样例 3 输入
3
1 2 3
8 4 3
9 2 6
样例 3 输出
2
样例 4 输入
6
1 4 4 4 2 5
1 22 3 444 5 666
7 88 9 10 111 12
样例 4 输出
4
数据范围
40% 的数据:;
100% 的数据:,。输入数据保证 个马力值两两不同。
相关
在下列比赛中: