【题目来源】
https://www.luogu.com.cn/problem/B3928
【题目描述】
你要和田忌赛马。你们各自有 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。
【输出格式】
输出一行，表示你最多能获胜几轮。
【输入样例一】
3
1 3 5
2 4 6
【输出样例一】
2
【输入样例二】
5
10 3 5 8 7
4 6 1 2 9
【输出样例二】
5
【数据范围】
1≤N≤5×10^4
【算法分析】
（一）田忌赛马模型 → “一对一匹配求最大获胜次数” 的贪心问题
● 田忌赛马模型的核心是“局部最优推导全局最优”，核心策略可总结为三句话（对应代码中的三个分支）：
（1）能赢则赢：用田忌当前最弱的马，去赢齐王当前最弱的马（不浪费强马，最大化赢的场次）；
（2）赢不了则消耗：如果田忌最弱的马赢不了齐王最弱的马，就用这匹弱马去消耗齐王最强的马（止损，避免强马被浪费在打弱马）；
（3）平局看强马：如果田忌最弱的马和齐王最弱的马平局，就看田忌最强的马：
☆ 若能赢齐王最强的马 → 用强马赢强马（赚 1 场）；
☆ 若赢不了 → 还是用弱马消耗齐王最强的马（避免平白亏）。
● 田忌赛马模型的关键细节
（1）排序必须是升序（方便用左指针指最弱、右指针指最强）；
（2）指针移动规则：“赢”则两个左指针右移、“消耗”则田忌左指针右移+齐王右指针左移、强马赢强马则两个右指针左移；
（3）循环终止条件：a_le<=a_ri（田忌的马匹配完）。
● 田忌赛马模型的核心记忆点：排序定强弱，双指针控匹配，弱马赢弱马，弱马耗强马。
（二）田忌赛马模型代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N]; //a:Tian Ji's horse, b:King Qi's horse
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
//Step 1: Sort in ascending order
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int a_le=1,a_ri=n; //Tian Ji's left and right indicators
int b_le=1,b_ri=n; //King Qi's left and right indicators
int win_cnt=0; //number of victories
//Step 2: Greedy Matching
while(a_le<=a_ri) {
if(a[a_le]>b[b_le]) win_cnt++,a_le++,b_le++;
else if(a[a_le]<b[b_le]) a_le++,b_ri--;
else {
if(a[a_ri]>b[b_ri]) win_cnt++,a_ri--,b_ri--;
else {
if(a[a_le]<b[b_ri]) a_le++,b_ri--;
else a_le++,b_le++;
}
}
}
cout<<win_cnt<<endl;
return 0;
}
/*
in:
5
10 3 5 8 7
4 6 1 2 9
out:
5
*/
【算法代码】
本题代码是 “田忌赛马” 问题的简化版。
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N],b[N];
int cnt,n;
int main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1,j=1; i<=n; i++) {
if(a[i]>b[j]) cnt++,j++;
}
cout<<cnt;
return 0;
}
/*
in:
5
10 3 5 8 7
4 6 1 2 9
out:
5
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/127443450
https://blog.csdn.net/ra90fy/article/details/144151505
https://www.luogu.com.cn/problem/solution/B3928