【题目来源】 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
