【田忌赛马模型】
（一）田忌赛马模型 → “一对一匹配求最大获胜次数” 的贪心问题
● 田忌赛马模型的核心是“局部最优推导全局最优”，核心策略可总结为三句话（对应代码中的三个分支）：
（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 horseint 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 ordersort(a+1,a+1+n);sort(b+1,b+1+n);int a_le=1,a_ri=n; //Tian Ji's left and right indicatorsint b_le=1,b_ri=n; //King Qi's left and right indicatorsint win_cnt=0; //number of victories//Step 2: Greedy Matchingwhile(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 9out:
5
*/
（三）田忌赛马模型简化版（洛谷 B3928：[GESP202312 四级] 田忌赛马）代码 →
#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 9out:
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