田忌赛马c++

2026/11/1 1:40:23

hello，今天我们又见面了✌，话不多说，开始吧！

题目描述

田忌和齐王各有 n 匹马，每匹马都有一个整数速度值。一次比赛恰好进行 n 局，每一局双方各派出一匹尚未出场的马，因此每匹马都恰好出场一次。

如果田忌的马速度更快，田忌获得 200 银币；如果两匹马速度相同，本局收益为 0；如果齐王的马速度更快，田忌失去 200 银币。

田忌知道双方所有马的速度，并可以重新安排自己的出场顺序。等价地，他可以在两组马之间选择一种一一配对。请计算田忌能够获得的最大总收益。

输入包含若干组比赛数据。

输入格式

每组数据的第一行包含一个正整数 n，表示双方各有 n 匹马。

第二行包含 n 个整数，表示田忌的马的速度。

第三行包含 n 个整数，表示齐王的马的速度。

所有数据之后有一行单独的整数 0，表示输入结束。这个 0 不是一组比赛数据。

输出格式

对于每组数据输出一行一个整数，表示田忌最多能获得多少银币。

输入样例 1

3 92 83 71 95 87 74 0

输出样例 1

样例说明

田忌可以让速度为 92 的马战胜速度为 87 的马，让速度为 83 的马战胜速度为 74 的马，再让速度为 71 的马输给速度为 95 的马。总收益为 200+200−200=200。

数据范围

对于每组比赛数据：

1≤n≤2000；
每匹马的速度均为 0 到 100 的整数。

数据特征

表中每一行表示：对于前 x% 的测试数据，该行列出的条件同时成立。

#include<bits/stdc++.h> using namespace std; int n,a[2005],b[2005],ans; int main(){ while(1){ ans=0; cin>>n; if(n==0)return 0; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) cin>>b[i]; sort(a+1,a+1+n); sort(b+1,b+1+n); int x1=1,x2=1,d1=n,d2=n; while(x1<=d1){ if(a[d1]>b[d2]){ ans++; d1--; d2--; } else{ if(a[x1]>b[x2])ans++,x1++,x2++; else if(a[x1]==b[d2])x1++,d2--; else ans--,x1++,d2--; } } cout<<ans*200<<endl; } return 0; }

题解

题意与数学模型

对每组数据，田忌和齐王各有 nn 匹马，每匹马都必须恰好出场一次。田忌可以重排自己的出场顺序，因此一个合法方案等价于在两组马之间建立一个一一配对。

设田忌的速度为 a1,…,ana1,…,an，齐王的速度为 b1,…,bnb1,…,bn。定义一局的单位收益为

w(x,y)= \begin{cases} 1,&x>y,\\ 0,&x=y,\\ -1,&xy.b_r$，让双方最快马比赛，田忌得到 $200$。 2. 否则，若 $a_l>b_l$，让双方最慢马比赛，田忌得到 $200$。 3. 否则，让田忌最慢马 $a_l$ 对阵齐王最快马 $b_r$。若 $a_lb_r$，田忌失去b_r$，则 $a_r$ 能战胜齐王所有尚未使用的马。考虑任意一个最优配对：设其中 $a_r$ 与 $b_j$ 配对，而 $b_r$ 与 $a_i$ 配对。把这两对改成 $(a_r,b_r)$ 和 $(a_i,b_j)$。前后 $a_r$ 都获胜；又因为 $b_j\le b_r$，同一匹 $a_i$ 对阵更慢的 $b_j$ 时，结果不会比对阵 $b_r$ 更差。交换不会降低总收益，所以第一种选择安全。 ### 最慢马可以取胜时若第一种情况不成立，而 $a_l>b_l$，那么齐王最慢马 $b_l$ 会输给田忌所有尚未使用的马。设某个最优配对中 $b_l$ 与 $a_i$ 配对，而 $a_l$ 与 $b_j$ 配对。交换为 $(a_l,b_l)$ 和 $(a_i,b_j)$ 后，对 $b_l$ 的胜局仍然保留。由于 $a_i\ge a_l$，用 $a_i$ 代替 $a_l$ 对阵同一匹 $b_j$，结果也不会变差。因此第二种选择同样可以出现在某个最优解中。 ### 其余情况可以牺牲最慢马进入第三种情况时，同时有 $a_r\le b_r$ 和 $a_l\le b_l$。田忌最慢马不可能战胜任何尚未使用的齐王马，而齐王最快马也不可能被任何田忌马战胜。在某个最优配对中，设 $a_l$ 与 $b_j$ 配对，$b_r$ 与 $a_i$ 配对。若 $a_lb_j$，那么a_l$，则交换后 $a_i$ 能战胜 $b_j$，新增的胜局足以补偿 $a_l$ 从平局变成失败。若 $a_l=b_r$，由排序关系可知所有剩余速度都相同，任意配对都为平局。因此第三种选择也不会排除所有最优解。三个分支都能确定一对属于某个最优解的马。删去该对后，剩余数组仍然有序且问题形式不变。对剩余马匹数量归纳，可知算法得到的总收益就是全局最大收益。 ## 实现细节 - 四个指针分别指向两个有序数组的左右端点，每轮恰好删除双方各一匹马。 - 第三个分支只有在 $a_l