PAT贪心算法田忌赛马

### 关于 PAT 考试中的田忌赛马问题

#### 田忌赛马问题描述
田忌赛马是一个经典的贪心算法题目，在这个问题中，给定了两组数据分别代表齐王和田忌的马的速度。比赛规则是双方各派出一匹马来进行一对一的比赛，胜利者得一分。目标是在已知对方马匹速度的情况下，通过合理的安排己方马匹出场顺序来获得尽可能多的分数。

#### 解题思路分析
对于此类问题可以采用如下策略：

- 将两个数组按照从大到小排序。
- 使用双指针方法比较两端的最大值或最小值来进行匹配决策。
- 如果当前最强的对手能赢，则让最弱的一匹去送死；如果不能赢，则用自己最强的一匹对抗之。

这种方法能够保证每次都能做出局部最优的选择从而达到全局最优的效果[^1]。

#### Python 示例代码实现
下面给出一段基于上述思想编写的Python程序用于模拟该过程:

def horse_racing(tian, wang):
    tian.sort(reverse=True)
    wang.sort(reverse=True)

    score = 0
    while tian and wang:
        if tian[-1] > wang[-1]:
            # 当田忌最快的马比齐王最快还快时，派这匹马上场赢得这一局
            score += 1
            tian.pop()
            wang.pop()
        elif tian[0] < wang[0]:
            # 否则，当田忌最慢的马输给齐王最慢的时候，
            # 让它上场输掉这一轮保存实力更强的马
            tian.pop(0)
            wang.pop()
        else:
            break
    
    return score


if __name__ == "__main__":
    n = int(input())
    tian = list(map(int, input().split()))
    wang = list(map(int, input().split()))

    result = horse_racing(tian[:], wang[:])
    print(result)