02287: Tian Ji -- The Horse Racing

greedy, dfs http://cs101.openjudge.cn/practice/02287

Here is a famous story in Chinese history.

That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others.

Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser.

Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian.

Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match.

It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king's regular, and his super beat the king's plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?

Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian's horses on one side, and the king's horses on the other. Whenever one of Tian's horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching...

However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses -- a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.

In this problem, you are asked to write a program to solve this special case of matching problem.

输入

The input consists of up to 50 test cases. Each case starts with a positive integer n ( n<=1000) on the first line, which is the number of horses on each side. The next n integers on the second line are the speeds of Tian's horses. Then the next n integers on the third line are the speeds of the king's horses. The input ends with a line that has a single `0' after the last test case.

输出

For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.

样例输入

样例输出

200
0
0

来源：Shanghai 2004

思路：经典的“双端贪心”策略

田忌赛马的最优策略可以归纳为“下等马对上等马”的变种。需要同时维护田忌和齐王手中最快和最慢的马。

将田忌的马 ( $T$ ) 和齐王的马 ( $K$ ) 分别从小到大排序。设田忌的当前马匹区间为 $[T_{s l o w}, T_{f a s t}]$ ，齐王的为 $[K_{s l o w}, K_{f a s t}]$ 。

决策流程（贪心策略）：

每次比赛一轮只看双方最快的马：

如果田忌最快的马 > 齐王最快的马 ( $T_{f a s t} > K_{f a s t}$ )：
- 直接赢。既然最强的能赢对方最强的，那就赢下来，保留实力较弱的马去对付对方弱的。
- 操作： $T_{f a s t}$ vs $K_{f a s t}$ ，胜。
如果田忌最快的马 < 齐王最快的马 ( $T_{f a s t} < K_{f a s t}$ )：
- 必须输。田忌最强的都赢不了齐王最强的，那田忌所有马都赢不了 $K_{f a s t}$ 。为了减少损失，用田忌最慢的马去消耗掉齐王最快的马。
- 操作： $T_{s l o w}$ vs $K_{f a s t}$ ，负。
如果田忌最快的马 == 齐王最快的马 ( $T_{f a s t} == K_{f a s t}$ )：
- 这时候不能草率平局，要回头看最慢的马。
- 3.1 如果田忌最慢的马 > 齐王最慢的马 ( $T_{s l o w} > K_{s l o w}$ )：
  - 赚了。用最差的马赢了对方最差的马，性价比极高。
  - 操作： $T_{s l o w}$ vs $K_{s l o w}$ ，胜。
- 3.2 否则（即 $T_{s l o w} \leq K_{s l o w}$ ）：
  - 既然最慢的赢不了对方最慢的，那这匹 $T_{s l o w}$ 几乎是废牌。用它去消耗齐王最快的 $K_{f a s t}$ （虽然会输，或者是平，但保住了 $T_{f a s t}$ 去打别人的机会）。
  - 注意：这里有一点细节，拿 $T_{s l o w}$ 去怼 $K_{f a s t}$ ，通常是输，但在极其特殊情况下（所有马速度都一样）是平。
  - 操作： $T_{s l o w}$ vs $K_{f a s t}$ 。

使用双指针（或 collections.deque）实现上述逻辑，代码非常简洁。

python

import sys


def solve():
    # 读取所有输入
    input_data = sys.stdin.read().split()
    it = iter(input_data)

    while True:
        n = int(next(it))
        if n == 0:
            break

        tian = [int(next(it)) for _ in range(n)]
        king = [int(next(it)) for _ in range(n)]

        # 1. 排序
        tian.sort()
        king.sort()

        # 2. 初始化双指针
        # 田忌的头尾指针
        t_slow, t_fast = 0, n - 1
        # 齐王的头尾指针
        k_slow, k_fast = 0, n - 1

        money = 0

        # 进行 N 轮比赛
        for _ in range(n):
            # 情况1: 田忌最快 > 齐王最快 -> 赢
            if tian[t_fast] > king[k_fast]:
                money += 200
                t_fast -= 1
                k_fast -= 1

            # 情况2: 田忌最快 < 齐王最快 -> 输（用最慢消耗对方最快）
            elif tian[t_fast] < king[k_fast]:
                money -= 200
                t_slow += 1
                k_fast -= 1

            # 情况3: 田忌最快 == 齐王最快 -> 比较慢马
            else:
                # 3.1 田忌最慢 > 齐王最慢 -> 赢（用慢马拿下一胜）
                if tian[t_slow] > king[k_slow]:
                    money += 200
                    t_slow += 1
                    k_slow += 1
                # 3.2 其他情况 -> 用田忌最慢消耗齐王最快
                else:
                    # 这里需要判断一下胜负平
                    if tian[t_slow] < king[k_fast]:
                        money -= 200
                    # 如果相等则不加不减（平局），例如全员速度一样的情况

                    t_slow += 1
                    k_fast -= 1

        print(money)


if __name__ == "__main__":
    solve()

4. 关键点解析

为什么排序？ 贪心算法的基础是建立在有序结构上的，通过排序可以清晰地知道当前的“最强战力”和“最弱战力”。
为什么平局时要比较慢马？ 如果只盯着快马看， $T_{f a s t} == K_{f a s t}$ 时犹豫不决（平局？还是留着？）。但如果看一眼慢马，如果 $T_{s l o w}$ 能赢 $K_{s l o w}$ ，那绝对是血赚（因为 $T_{s l o w}$ 本来也就是个炮灰，现在居然能拿分）。如果 $T_{s l o w}$ 赢不了，那它就是纯炮灰，赶紧让它去送死（消耗掉 $K_{f a s t}$ ），从而保护我方 $T_{f a s t}$ 以后可能赢或平 $K_{f a s t - 1}$ 。
复杂度：
- 时间复杂度： $O (N \log N)$ ，主要消耗在排序上。遍历过程是 $O (N)$ 。这对于 $N$ 较大的情况也完全适用。
- 空间复杂度： $O (N)$ ，用于存储马匹速度。

这个优化版本不仅代码行数减少，逻辑也更加清晰，是解决这类博弈类贪心问题的标准范式。

2020fall-cs101，顾臻宜。解题思路：以max 赢max，以min 赢min，以min 输max；不断del更新。一开始看群里讨论以为分行输入是指一行田忌一行国王交替进行，就是不AC；出门吹了会冷风之后回来又试了一次田忌所有的数据分行输完、再国王，AC了。

对第33行田忌小马对国王大马的解释。if 田忌大马等于国王大马 and 田忌小马等于国王小马的情况。1）此时用田忌小马对国王大马，至少不亏，所以采取这步。2）因为此时，如果是田忌大马对国王大马，得0分；田忌小马对国王小马，得0分。如果用田忌小马对国王大马，得-1分；田忌大马对国王小马，可能得1分；-1+1，是不亏的。但是后续可能更有优势，因为可以用田忌大马对国王次大马。

2021fall-cs101，欧阳韵妍。对于我来说比较困难的就是当两人的马速度相等时该如何处理，一开始老是想着要直接把相等时的情况考虑清楚，后来看了一眼题解才发现可以先把相等的情况放一放，先去比较最小的马，通过把最小的马拉出来和王的最大的马比较来破解相等的情况。这道题让我学会了间接破解困境。

python

for _ in range(50):
    n = int(input())
    if n==0:
        break
    A = [[], []]
    for _ in range(n):							# 田忌赛马这个题目，测试数据更新过，已经不用这么复杂来接收。常用读入数据的方法就可以。
        for x in input().split():
            A[0].append(int(x))
        if len(A[0]) == n:
            break
    for _ in range(n):
        for y in input().split():
            A[1].append(int(y))
        if len(A[1]) == n:
            break
    
    A[0].sort(reverse=True)
    A[1].sort(reverse=True)
    
    answer = 0
    
    for _ in range(n):
        if A[0][0] > A[1][0]:
            answer += 1
            del A[0][0]
            del A[1][0]
        else:
            if A[0][-1] > A[1][-1]:
                answer += 1
                del A[0][-1]
                del A[1][-1]
            else:
                if A[0][-1] < A[1][0]:
                    answer -= 1
                del A[0][-1]
                del A[1][0]
    
    print(200*answer)

找到恰好能赢的马，如果找不到就拿他对决对方最强的。

2021fall-cs101，陈贝宁。

粗略的证明如下：首先看双方最小的马，如果我们能赢，那么我们的所有马都能赢，为了节省实力，用最小的马比；如果不能赢（输or平），那么就用这匹马当炮灰，输掉对面最大的马；但是这里有个问题：如果我们最大的马能赢对面最大的马，那么那小马输大马、大马赢小马（-1+1）就比拿大马赢大马、小马平小马（+1+0）要亏，所以要插入判断一下我们的大马能不能赢。

这里还用到了双指针，虽然用del更省事但是主要是怕出乱子。

python

while True:
    n = int(input())
    if n==0: 
        break
    
    *Tian, = map(int, input().split())
    *King, = map(int, input().split())
    Tian.sort()
    King.sort()
    
    lTian = 0; rTian = n - 1
    lKing = 0; rKing = n - 1
    ans = 0
    while lTian <= rTian:
        if Tian[lTian] > King[lKing]:
            ans += 1;
            lTian += 1
            lKing += 1
        elif Tian[rTian] > King[rKing]:
            ans += 1
            rTian -= 1
            rKing -= 1
        else:
            if Tian[lTian] < King[rKing]:
                ans -= 1
            
            lTian += 1
            rKing -= 1
    
    print(ans*200)

2021fall-cs101，吉祥瑞。

解题思路：贪心方法不好想，于是改用DP（受《算法图解》中画格子的方法的启发）。第一步，转化为连线问题，设田忌赢、平局、输对应线的权重为2、1、0，权重和为c，有n匹马，则田忌得到的钱为 $200 (c - n)$ ，因为，如果赢x局，平y局，则得钱 $200 x - 200 (n - x - y) = 200 (2 x + y - n) = 200 (c - n)$ 。第二步，预处理，对马的速度降序排序。第三步，设只考虑田忌的前i 匹马和齐王的前j 匹马的情况下的最大权重和为$c[i][j] $，则$ c[i][j] = max(c[i-1][j], c[i][j-1], c[i-1][j-1]+w)$ ，其中w 是i 和j 的连线的权重，注意设好边界条件$c[0][0] = c[i][0] = c[0][j] = 0 $。

闫先生评：《算法图解》的 OJ23421.小偷背包，可以 OJ02773.采药，还可以 OJ02287.田忌赛马。高！

python

while True:
    n = int(input())
    if n == 0:
        break
    a = sorted([int(x) for x in input().split()], reverse=True)
    b = sorted([int(x) for x in input().split()], reverse=True)
    c = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if a[i - 1] > b[j - 1]:
                w = 2
            elif a[i - 1] == b[j - 1]:
                w = 1
            else:
                w = 0
            c[i][j] = max(c[i - 1][j], c[i][j - 1], c[i - 1][j - 1] + w)
    print((c[n][n] - n) * 200)

动态规划（DP）解法 是对田忌赛马问题的一种非常巧妙且通用的建模方式，尤其适合那些觉得贪心策略“不好想”或“难以证明正确性”的同学。下面来 逐层解读这个 DP 的状态定义、转移方程、边界条件，并解释其为何有效。

一、问题转化：从“赛马”到“连线匹配”

原始规则：

每匹马只能用一次。
共 n 轮，每轮田忌和齐王各出一匹马。
赢 +200，平 0，输 -200。

关键观察：

设：

赢 x 局 → +200x
平 y 局 → 0
输 z = n - x - y 局 → -200z

总收益： $$ 200x - 200(n - x - y) = 200(2x + y - n) $$

令权重：

赢 → 权重 2
平 → 权重 1
输 → 权重 0

则总权重 $ c = 2x + y $，于是： $$ \text{最终钱数} = 200(c - n) $$

目标转化为：最大化权重和 c。

二、DP 状态设计

将问题看作：在两个有序序列之间画不相交的连线（一一匹配），使得总权重最大。

排序策略：降序排序

python

a = sorted([...], reverse=True)  # 田忌马速
b = sorted([...], reverse=True)  # 齐王马速

为什么降序？因为 DP 中我们按“前 i 匹”考虑，从强到弱处理更自然（也可以升序，但需调整逻辑）。
排序不影响最优解，因为匹配是任意的（可以重新排列顺序）。

状态定义：

c[i][j] = 考虑 田忌前 i 匹最强马 和 齐王前 j 匹最强马 时，能获得的 最大权重和。

注意：这里 不要求 i == j！这是关键——它允许“跳过”某些马（即暂时不匹配），但最终我们要的是 c[n][n]（全部匹配）。

三、状态转移方程详解

对于 c[i][j]，有三种选择：

不使用田忌第 i 匹马

→ 相当于只考虑前 i-1 匹田忌马 vs 前 j 匹齐王马 → 值为 c[i-1][j]

不使用齐王第 j 匹马

→ 只考虑前 i 匹田忌马 vs 前 j-1 匹齐王马 → 值为 c[i][j-1]

让田忌第 i 匹马对阵齐王第 j 匹马

→ 必须同时消耗两者，权重为 w（2/1/0） → 值为 c[i-1][j-1] + w

因此：

python

c[i][j] = max(
    c[i-1][j],           # 跳过田忌第 i 匹
    c[i][j-1],           # 跳过齐王第 j 匹
    c[i-1][j-1] + w      # 匹配 (i, j)
)

边界条件：

python

c[0][j] = 0  # 没有田忌马，权重为0
c[i][0] = 0  # 没有齐王马，权重为0
c[0][0] = 0

⚠️ 注意：虽然中间状态 i ≠ j 是允许的，但最终必须匹配所有马，所以答案是 c[n][n]。为什么这样能保证“完美匹配”？因为只有当 i == j == n 时，才用了全部马；而转移过程中，匹配操作（第三项）是唯一能同时推进 i 和 j 的方式，其他两项只是“延迟匹配”。最终 DP 会自动选择一条路径，使得恰好匹配 n 对。

四、为什么这个 DP 是正确的？

核心思想：最长公共子序列（LCS）的变种

这个 DP 结构和 LCS 完全一样！
区别在于：LCS 的“匹配”得 1 分，这里根据数值大小得 2/1/0 分。
由于我们允许跳过元素（通过前两项），但最终必须全部匹配（通过取 c[n][n]），所以它实际上是在所有可能的一一匹配中找最大权重。

举例说明：

假设 a = [3, 2, 1], b = [3, 2, 1]（已降序）

若直接一一对应：(3,3)=1, (2,2)=1, (1,1)=1 → c=3 → 得 0 元
但若错位：(3,2)=2, (2,1)=2, (1,3)=0 → c=4 → 得 200 元

DP 会通过比较不同跳过/匹配组合，找到后者。

五、复杂度分析

时间：O(n²)
空间：O(n²)（可优化到 O(n)，但没必要）

对于 n ≤ 1000（本题 n ≤ 50），完全足够。

六、与贪心解法的关系

方法	思路	优点	缺点
贪心（双指针）	利用问题特殊性质（全序、三值权重）	O(n log n)，极快	需要洞察力，不易推广
DP（格子法）	通用匹配模型，类似 LCS	思路直观，易写，可推广到更多权重	O(n²)，稍慢

✨ 七、代码再审视

python

for i in range(1, n+1):
    for j in range(1, n+1):
        if a[i-1] > b[j-1]:
            w = 2
        elif a[i-1] == b[j-1]:
            w = 1
        else:
            w = 0
        c[i][j] = max(c[i-1][j], c[i][j-1], c[i-1][j-1] + w)

完全正确！降序排序确保“前 i 匹”是最强的 i 匹，不影响最优匹配的存在性（因为匹配是任意的）。最终 (c[n][n] - n) * 200 正确还原金钱。

总结

这个 DP 解法的精妙之处在于：

将博弈问题转化为带权二分图匹配；
利用二维 DP 模拟“选择/跳过/匹配”决策；
借用 LCS 的经典框架，轻松解决看似复杂的策略问题。

对于“贪心想不出”的题目，DP + 合理状态设计 往往是救命稻草。而田忌赛马正好展示了：同一个问题，既可以用天才的贪心，也可以用朴实的 DP —— 这正是算法之美！

如果你以后遇到类似“两序列配对、求最优得分”的问题，不妨先想想：能不能画个格子，用 DP 解？

田忌最快马与王最快马一样，是下面程序（3）的情况。为什么程序中不用考虑田忌最慢马与王最慢马一样的情况？考虑田忌最慢马与王最慢马一样的情况：

1）最快一样的都对掉，最慢一样的对掉。极端情况是俩俩匹配的都相等，则最后得0分。但是

2）如果田忌最慢对掉王最快，-1，田忌最快对王次快，+1。这样下去，最后结果可能是 >=0，有优势。

因为优势，所以不用考虑田忌最慢马与王最慢马一样的情况，相当于pass。此时，只要田忌最慢对掉王最快。保持优势，进入下一轮循环，还会重新来判断田忌最快和王最快。

c++

//田忌赛马 — 贪心算法1
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, tian[1010], king[1010];
    while (scanf("%d", &n) && n) {
        for(int i=0; i<n; ++i)
            scanf("%d", &tian[i]);
        for(int i=0; i<n; ++i)
            scanf("%d", &king[i]);
        sort(tian, tian+n);
        sort(king, king+n);
        
        int ans = 0, max1 = n-1, max2 = n-1, min1 = 0, min2 = 0, cnt = 0;
        while((cnt++) < n) {
            if(tian[max1] > king[max2]) { // （1）田忌最快马比齐威王最快马快
                ans += 200; // 直接比
                max1--;
                max2--;
            } else if(tian[max1] < king[max2]) { // （2）田忌最快马比齐威王最快马慢
                ans -= 200; // 用田忌最慢的马比
                min1++;
                max2--;
            } else { // （3）田忌的最快马和齐威王的最快马速度一样快
                if(tian[min1] > king[min2]) { // 1）田忌最慢马比齐威王最慢马快
                    ans += 200; // 直接比
                    min1++;
                    min2++;
                } else { // 田忌最慢马比齐威王最快马慢
                     if(tian[min1] < king[max2])  // 2）田忌最慢马比齐威王最快马慢
                        ans -= 200; // 用田忌最慢的马比
                    
                     min1++;
                     max2--;  
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

【马铉钦，25化院】dfs思路：考虑我们的最差的马：如果能赢对方最差的就赢，会输对面最差就拿来打对面最强，平局需要考虑两种情况，从此递归；注意多组数据需要清理缓存

python

import sys
from functools import lru_cache
sys.setrecursionlimit((2**30)-1)
r=iter(sys.stdin.read().split())

@lru_cache(maxsize=None)
def sol(le1,ri1,le2,ri2):
    
    if le1==n:
        return 0
    if li1[le1]>li2[le2]:
        return sol(le1+1,ri1,le2+1,ri2)+1
    elif li1[le1]<li2[le2]:
        return sol(le1+1,ri1,le2,ri2-1)-1
    elif li1[le1]==li2[le2]:
        if li2[ri2]>li1[le1]:
            return max(sol(le1+1,ri1,le2+1,ri2),sol(le1+1,ri1,le2,ri2-1)-1)
        else:
            return sol(le1+1,ri1,le2+1,ri2)

    
while True:
    n=int(next(r))
    if n==0:
        break
    sol.cache_clear()
    li1=sorted([int(next(r)) for _ in range(n)])
    li2=sorted([int(next(r)) for _ in range(n)])
   
    print(200*sol(0,n-1,0,n-1))

把上面dfs代码优化一下

python

import sys
sys.setrecursionlimit(10**7)
r = iter(sys.stdin.read().split())

from functools import lru_cache

while True:
    n = int(next(r))
    if n == 0:
        break

    t = sorted(int(next(r)) for _ in range(n))
    q = sorted(int(next(r)) for _ in range(n))

    @lru_cache(None)
    def dp(l1, r1, l2, r2):
        if l1 > r1:
            return 0

        a = t[l1]      # 我方最差
        b = q[l2]      # 对方最差

        # --- 我最差 > 对方最差：必胜 ---
        if a > b:
            return dp(l1+1, r1, l2+1, r2) + 1

        # --- 我最差 < 对方最差：必输 ---
        if a < b:
            return dp(l1+1, r1, l2, r2-1) - 1

        # --- 平局情况 ---
        # a == b
        # 若对方最强 > 我最差：需要比较 “平” 与 “拿去输”
        if q[r2] > a:
            return max(
                dp(l1+1, r1, l2+1, r2),         # 当作平局
                dp(l1+1, r1, l2, r2-1) - 1      # 当作拿去输
            )
        else:
            # 否则对方最强也 == a，必平
            return dp(l1+1, r1, l2+1, r2)

    print(200 * dp(0, n-1, 0, n-1))

dfs

python

# 赵时阳-数院23

from functools import lru_cache
import sys
sys.setrecursionlimit(1 << 30)


def compare(a, b):
    if a > b:
        return 1
    elif a == b:
        return 0
    else:
        return -1

while True:
    n = int(input())
    if n == 0: 
        break

    tian_values = list(map(int, input().split()))
    king_values = list(map(int, input().split()))
    tian_values.sort()
    king_values.sort()

    @lru_cache(maxsize=2048)
    def dfs(start, end, i):
        if i < n:
            tian_value = tian_values[i]
            king_value_start = king_values[start]
            x1 = dfs(start + 1, end, i + 1) + compare(tian_value, king_value_start)
            
            king_value_end = king_values[end]
            x2 = dfs(start, end - 1, i + 1) + compare(tian_value, king_value_end)  
            x = max(x1, x2)
            return x
        else:
            return 0

    result = dfs(0, n - 1, 0)
    print(200 * result)

dfs(start, end, i) 函数：这是一个深度优先搜索函数，用来寻找最佳的马匹匹配方案。它使用了@lru_cache装饰器来缓存中间结果，减少不必要的计算。
参数start和end分别表示当前考虑的国王马匹的起始和结束索引。
参数i表示当前正在考虑的田忌马匹的索引。
函数尝试两种情况：一是让田忌的当前马匹与国王的最低速马匹比赛；二是让田忌的当前马匹与国王的最高速马匹比赛。根据比赛结果选择得分更高的方案。

让我们分析这段代码的时间复杂度。
代码分析
dfs函数:
dfs 是一个递归函数，使用了 @lru_cache（一个带有缓存功能的函数装饰器）。
每次调用时，它接受 start、end 和 i 作为参数，其中：
start 和 end 是范围的两端指针。
i 是当前正在处理的田忌的马匹索引。
递归终止条件是当 i >= n 时返回 0。
参数空间:
start 的可能值范围是 [0, n-1]。
end 的可能值范围是 [0, n-1]。
i 的可能值范围是 [0, n-1]。
总状态数 = $ n \times n \times n$ = O(n^3) 。
递归每步的复杂度:
每个状态只需要进行一次简单的比较和递归调用，不涉及额外循环，因此单次递归调用是 O(1) 。
缓存的作用:
使用 lru_cache，避免了对重复状态的重复计算，因此每个状态最多计算一次。
总时间复杂度
每个状态的计算复杂度为 O(1) ，总共有 O(n^3) 个状态。
因此，该算法的时间复杂度为 O(n^3) 。
空间复杂度
递归栈空间:
递归调用深度最多为 O(n) 。
缓存空间:
缓存的状态数为 O(n^3) 。
总空间复杂度为 O(n^3) 。
代码的优化潜力
如果 n 较大（例如 n > 100 ），时间复杂度 O(n^3) 可能过高，可以考虑使用动态规划优化，减少维度或重复计算。

python

from functools import lru_cache
import sys

sys.setrecursionlimit(1 << 30)

def compare(a, b):
    if a > b:
        return 1
    elif a == b:
        return 0
    else:
        return -1

while True:
    n = int(input())
    if n == 0:
        break

    tian_values = sorted(map(int, input().split()))
    king_values = sorted(map(int, input().split()))

    @lru_cache(maxsize=4096)
    def dfs(start, end, i):
        if i == n:
            return 0
        # 当前田忌的马匹
        tian_value = tian_values[i]
        # 齐王马匹的两种选择：前端或后端
        return max(
            dfs(start + 1, end, i + 1) + compare(tian_value, king_values[start]),
            dfs(start, end - 1, i + 1) + compare(tian_value, king_values[end])
        )

    # 计算结果并输出
    result = dfs(0, n - 1, 0)
    print(200 * result)

#include <stdio.h>
#include <string.h>

#define MAX_N 1000 // 你可能需要根据问题限制修改这个值
#define WIN 200 // 每场胜利所得到的分数

int tian_values[MAX_N], king_values[MAX_N];
int dp[MAX_N][MAX_N];

int compare(int a, int b) {
    if (a > b) return 1;
    else if (a == b) return 0;
    else return -1;
}

int dfs(int start, int end, int i, int n) {
    if (i >= n) return 0; // 基础情况

    if (dp[start][end] != -1) return dp[start][end]; // 若已计算过此子问题则直接返回结果

    int tian_value = tian_values[i];
    int king_value_start = king_values[start];
    int x1 = dfs(start + 1, end, i + 1, n) + compare(tian_value, king_value_start);
    
    int king_value_end = king_values[end];
    int x2 = dfs(start, end - 1, i + 1, n) + compare(tian_value, king_value_end);

    dp[start][end] = (x1 > x2) ? x1 : x2; // 存储计算结果
    return dp[start][end];
}

int main() {
    int n, i;
    while (scanf("%d", &n) && n) {
        memset(dp, -1, sizeof(dp)); // 初始化dp数组

        for (i = 0; i < n; i++) scanf("%d", &tian_values[i]);
        for (i = 0; i < n; i++) scanf("%d", &king_values[i]);

        for (i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (tian_values[i] > tian_values[j]) {
                    int temp = tian_values[i];
                    tian_values[i] = tian_values[j];
                    tian_values[j] = temp;
                }
                if (king_values[i] > king_values[j]) {
                    int temp = king_values[i];
                    king_values[i] = king_values[j];
                    king_values[j] = temp;
                }
            }
        }

        int result = dfs(0, n - 1, 0, n);
        printf("%d\n", result * WIN);
    }
    return 0;
}

python

"""
侯树宽 24元培学院
思路：用二分查找让能赢的马都以最小的优势赢，剩下的马都是平局和输的，
减去平局数即为输的局数
"""
from bisect import bisect_left
while True:
    n = int(input())
    if n == 0:
        break
    tians = [int(x) for x in input().split()]
    kings = [int(x) for x in input().split()]
    tians.sort()
    kings.sort()
    ties = []
    count = 0
    for p1head in range(n):
        a = bisect_left(kings,tians[p1head])
        if a:
            count += 1
            kings.pop(a-1)
        else:
            ties.append(tians[p1head])
    p2 = 0
    for i in range(len(ties)):
        if ties[i] < kings[p2]:
            count -= 1
        else:
            p2 += 1

    print(count*200)

【沈俊丞25工院】逻辑是：认为田忌每一次获胜都有一定“损耗”；这个损耗没有量化，但是足以成为构思思路。例如，若田忌拿到22 21 20，齐王拿到23 22 20，那么田忌用22去对决20，损耗就大于用21对决20。损耗越大，接下来的对决就越不利。我们希望田忌尽可能多赢，同时赢的损耗最低。我们把赢、平、输分开讨论。为什么这样讨论有效呢？我们考虑不存在平局情况的状态，现在给两人各塞一匹速度相等的马，田忌的最大赢面只会增长，不会减小。所以对田忌来说，他希望把这匹马最大化地利用，这匹马给他赢得更多。这样，我们一开始不讨论平，先讨论这匹马赢的可能；如果实在没法赢，让它平也不亏。

整个代码就是这样组织的：在讨论田忌赢的情况时利用指针的进退让田忌赢得尽可能多，同时在每一次赢上面都损耗最小，这是经典的贪心。接着，田忌已经赢无可赢，他剩下最快的马不可能比齐王剩下最慢的马快，所以从田忌最快和齐王最慢两端考虑平局。最后，剩下的马都只能输了。

思路和侯树宽 24元培学院类似但是没有用二分查找

python

while True:
    n = int(input())
    if n == 0: break
    T = list( map(int,input().split()) )
    K = list( map(int,input().split()) )
    T.sort(reverse=True)
    K.sort(reverse=True)
    i,j = 0,0
    cnt = 0

    #所有获胜情况
    while i < n and j < n:  
        if T[i] > K[j]:
            cnt += 1
            while i < n-1 and T[i+1] > K[j]:  
                i += 1
                #保证赢的情况下令损耗最小
            del T[i]
            del K[j]
            n -= 1
            if i == n: i -= 1
        elif i > 0 and T[i-1] > K[j]:
            cnt += 1
            del T[i-1]
            del K[j]
            n -= 1
            i -= 1
        elif T[i] <= K[j]:
            j += 1

    #所有平局情况
    while T and T[0] == K[-1]: 
        del T[0]
        del K[-1]

    #所有失败情况
    cnt -= len(T) 
    
    print(cnt*200)

思路：我们的思路是能赢就赢，因此先看田和国王的最快的马和最慢的马，如果此时田能赢，就赢，如果不能赢或平局，就用田的最慢的马来消耗国王最快的马（在平局的情况下，最坏的可能是一正一负，但此时对国王的消耗最大此后赢得可能性将提高），直到能赢为止。在这种思路下我们程序的逻辑就相当简单了，只需要额外考虑田和国王剩下的马的速度都一样的情况（即样例2），此时剩下的比赛将全部平局

python

# 谭皓文 24工院
def sai(tian, king, num):
    money = 0
    i = 0;
    j = 0;
    k = num - 1;
    l = num - 1
    while True:
        if tian[k] > king[l]:
            k -= 1;
            l -= 1;
            money += 200
        elif tian[i] > king[j]:
            i += 1;
            j += 1;
            money += 200
        else:
            if tian[i] == tian[k] == king[j] == king[l]:
                return money
            else:
                i += 1;
                l -= 1;
                money -= 200
        if i > k:
            break
    return money


while True:
    n = int(input())
    if n == 0:
        break
    t = sorted(list(map(int, input().split())))
    k = sorted(list(map(int, input().split())))
    print(sai(t, k, n))

思路：

感谢信科24级程沐阳同学
在我为平局情况抓耳挠腮时，哥们告诉我：最优情况只能出现在以下情况中：
1. 田1对王1，田2对王2，田3对王3......
2. 田2对王1，田3对王2，田4对王3......
3. 田3对王1，田4对王2，田5对王3......
4. ......
我一想，确实有道理，瞬间感觉像被扇了一巴掌一样，在饭桌上掏出电脑完成了本题
甚至只有8行

python

# 颜鼎堃 24工学院
while(n := int(input())):
    tian = sorted(map(int, input().split()))
    wang = sorted(map(int, input().split()))
    ans = [0 for i in range(n)]
    for i in range(n):
        for j in range(n):
            ans[i] += (tian[(j + i) % n]-wang[j]) // abs(tian[(j + i) % n]-wang[j]) if tian[(j + i) % n] != wang[j] else 0
    print(200 * max(ans))

输入处理
python
while(n := int(input())):
这是一个无限循环，每次读取一个整数 n，表示马的数量。
n := int(input()) 是 Python 3.8 引入的赋值表达式（walrus operator），可以在条件语句中同时赋值和判断。
当 n 为 0 时，输入结束，循环终止。
计算每种匹配方式的得分
外层循环 i 表示不同的匹配方式，共有 n 种。
内层循环 j 遍历每一对马的比拼。
tian[(j + i) % n] 表示田忌的第 (j + i) % n 匹马。
wang[j] 表示国王的第 j 匹马。
计算得分：
如果 tian[(j + i) % n] > wang[j]，得分为 1。
如果 tian[(j + i) % n] < wang[j]，得分为 -1。
如果 tian[(j + i) % n] == wang[j]，得分为 0。
使用 (tian[(j + i) % n] - wang[j]) // abs(tian[(j + i) % n] - wang[j]) 来计算得分，当两者相等时返回 0。

02287: Tian Ji -- The Horse Racing ​

02287: Tian Ji -- The Horse Racing