A34437. 田忌赛马问题描述你要和田忌赛马。你们各自有 N 匹马，并且要进行 N 轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。你的马匹的速度分别为 u1,u2,........un，田忌的马匹的速度分别为u1,u2,........un。田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛 ？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现平局。输入描述第一行一个整数 N 。…
填空题
较难
知识点
题目描述
田忌赛马
问题描述
你要和田忌赛马。你们各自有 N 匹马，并且要进行 N 轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。
你的马匹的速度分别为 u1,u2,........un，田忌的马匹的速度分别为u1,u2,........un。田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛 ？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现平局。
输入描述
第一行一个整数 N 。保证 1≤ N ≤ 50000。
接下来一行N个用空格隔开的整数，依次为 u1,u2,........un，表示你的马匹们的速度。保证 1≤ ui ≤2N。
接下来一行N个用空格隔开的整数，依次为 u1,u2,........un，表示田忌的马匹们的速度。保证 1≤ ui ≤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参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], t;
int b[N], h;
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &b[i]);
}
h = 1;
t = 0;
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
int ans = 0;
for (int i = 1; i <= n; ++i)
if (a[i] > b[h])
++ans, ++h;
printf("%d\n", ans);
return 0;
}
上一题
下一题