GESP认证C++编程真题解析 | B3928 [GESP202312 四级] 田忌赛马

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3928 GESP202312 四级] 田忌赛马 - 洛谷

【题目描述】

你要和田忌赛马。你们各自有N NN匹马，并且要进行N NN轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。

你的马匹的速度分别为u 1 , u 2 , ⋯ ， u n u_1,u_2,\cdots，u_nu1​,u2​,⋯，un​，田忌的马匹的速度分别为v 1 , v 2 , ⋯ , v n v_1,v_2,\cdots,v_nv1​,v2​,⋯,vn​。田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现平局。

【输入】

第一行一个整数N NN。保证1 ≤ N ≤ 5 × 1 0 4 1\le N \le 5\times 10^41≤N≤5×104

接下来一行N NN个用空格隔开的整数，依次为u 1 , u 2 , ⋯ , u n u_1,u_2,\cdots,u_nu1​,u2​,⋯,un​，表示你的马匹们的速度。保证1 ≤ u i ≤ 2 N 1\le u_i\le 2N1≤ui​≤2N。

接下来一行N NN个用空格隔开的整数，依次为v 1 , v 2 , ⋯ , v n v_1,v_2,\cdots,v_nv1​,v2​,⋯,vn​，表示田忌的马匹们的速度。保证1 ≤ v i ≤ 2 N 1\le v_i\le 2N1≤vi​≤2N。

【输出】

输出一行，表示你最多能获胜几轮。

【输入样例】

3 1 3 5 2 4 6

【输出样例】

2

【算法标签】

《洛谷 B3928 田忌赛马》 #贪心# #排序# #双指针two-pointer# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=50005;// 最大数组长度intn;// 数组大小intans;// 答案：满足条件的配对数量intu[N],v[N];// 两个数组intmain(){// 输入数组大小cin>>n;// 输入并排序数组ufor(inti=1;i<=n;i++){cin>>u[i];}sort(u+1,u+n+1);// 输入并排序数组vfor(inti=1;i<=n;i++){cin>>v[i];}sort(v+1,v+n+1);// 双指针贪心匹配intj=1;// v数组的指针for(inti=1;i<=n;i++)// 遍历u数组{// 如果当前u[i]大于等于当前v[j]，可以配对if(u[i]>=v[j]){j++;// 移动v指针ans++;// 成功配对数加1}// 如果u[i] < v[j]，这个u[i]无法匹配任何v// 不移动j，尝试用更大的u[i+1]来匹配v[j]}// 输出结果cout<<ans<<endl;return0;}

【运行结果】

3 1 3 5 2 4 6 2