田忌赛马模型 ← 双指针 + 排序 + 贪心

【田忌赛马模型】 （一）田忌赛马模型 → “一对一匹配求最大获胜次数” 的贪心问题 ● 田忌赛马模型的核心是“局部最优推导全局最优”，核心策略可总结为三句话（对应代码中的三个分支）： （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
*/

（三）田忌赛马模型简化版（洛谷 B3928：[GESP202312 四级] 田忌赛马）代码 → https://blog.csdn.net/hnjzsyjyj/article/details/158039999

#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/158039999 https://blog.csdn.net/hnjzsyjyj/article/details/127443450 https://blog.csdn.net/ra90fy/article/details/144151505 https://www.luogu.com.cn/problem/solution/B3928