田忌赛马4级T2 2023.12

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】
你要和田忌赛马 。你们各自有 N 匹马 ,并且要进行 N 轮比赛 ,每轮比赛 ,你们都要各派出一匹马决出胜负。你的马匹的速度分别为 U1 , U2 … UN , 田忌的马匹的速度分别为 V1,V2 … VN 。 田忌会按顺序派出他的马匹 ,请问 你要如何排兵布阵 ,才能赢得最多轮次的比赛?巧合的是 ,你和田忌的所有马匹的速度两两不同, 因此不可能出现平局。
【输入描述】
第一行一个整数 N 。保证 1 ≤ N ≤ 5 × 10^4 。
接下来一行 N 个用空格隔开的整数 ,依次为 U1,U2 … UN ,表示你的马匹们的速度 。
保证 1 ≤ Ui≤2N。
接下来一行 N 个用空格隔开的整数 ,依次为 V1 ,V2,… ,VN ,表示田忌的马匹们的速度 。
保证 1 ≤ Vi ≤2N。
【输出描述】
输出一行 ,表示你最多能获胜几轮。

【样例输入1】
3
1 3 5
2 4 6
【样例输出1】
2
【样例解释1】
第 1 轮, 田忌派出速度为 2 的马匹 ,你可以派出速度为 3 的马匹迎战 ,本轮你获胜。
第 2 轮, 田忌派出速度为 4 的马匹 ,你可以派出速度为 5 的马匹迎战 ,本轮你获胜。
第 3 轮, 田忌派出速度为 6 的马匹 ,你可以派出速度为 1 的马匹迎战 ,本轮田忌获胜。
如此 ,你可以赢得 2 轮比赛。
【样例输入2】
5
10 3 5 8 7
4 6 1 2 9
【样例输出2】
5

春季班中级4.20

未参加
状态
已结束
规则
ACM/ICPC
题目
12
开始于
2024-04-20 08:00
结束于
2024-05-02 20:00
持续时间
300.0 小时
主持人
参赛人数
25