【田忌赛马模型】一田忌赛马模型 → “一对一匹配求最大获胜次数” 的贪心问题● 田忌赛马模型的核心是“局部最优推导全局最优”核心策略可总结为三句话对应代码中的三个分支1能赢则赢用田忌当前最弱的马去赢齐王当前最弱的马不浪费强马最大化赢的场次2赢不了则消耗如果田忌最弱的马赢不了齐王最弱的马就用这匹弱马去消耗齐王最强的马止损避免强马被浪费在打弱马3平局看强马如果田忌最弱的马和齐王最弱的马平局就看田忌最强的马☆ 若能赢齐王最强的马 → 用强马赢强马赚 1 场☆ 若赢不了 → 还是用弱马消耗齐王最强的马避免平白亏。● 田忌赛马模型的关键细节1排序必须是升序方便用左指针指最弱、右指针指最强2指针移动规则“赢”则两个左指针右移、“消耗”则田忌左指针右移齐王右指针左移、强马赢强马则两个右指针左移3循环终止条件a_lea_ri田忌的马匹配完。● 田忌赛马模型的核心记忆点排序定强弱双指针控匹配弱马赢弱马弱马耗强马。二田忌赛马模型代码#include bits/stdc.h using namespace std; const int N1e55; int a[N],b[N]; //a:Tian Jis horse, b:King Qis horse int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; //Step 1: Sort in ascending order sort(a1,a1n); sort(b1,b1n); int a_le1,a_rin; //Tian Jis left and right indicators int b_le1,b_rin; //King Qis left and right indicators int win_cnt0; //number of victories //Step 2: Greedy Matching while(a_lea_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; } } } coutwin_cntendl; 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 N5e45; int a[N],b[N]; int cnt,n; int main() { cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; sort(a1,an1); sort(b1,bn1); for(int i1,j1; in; i) { if(a[i]b[j]) cnt,j; } coutcnt; return 0; } /* in: 5 10 3 5 8 7 4 6 1 2 9 out: 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/158039999https://blog.csdn.net/hnjzsyjyj/article/details/127443450https://blog.csdn.net/ra90fy/article/details/144151505https://www.luogu.com.cn/problem/solution/B3928