贪心算法（田忌赛马）

### 贪心算法解决田忌赛马问题

#### 问题描述
齐威王和田忌各有三匹不同等级的马，分别为上、中、下三个级别。每场比赛双方各派出一匹马进行比赛，胜利者获得一分。由于齐威王每一级别的马都比田忌相应级别的马要强，如果按照同级对阵的方式，则田忌必定失败。

为了使田忌能够赢得更多场次的比赛，在此引入贪心算法来优化马匹之间的匹配方式[^1]。

#### 算法设计
通过调整田忌方马匹出场顺序，利用贪心策略确保尽可能多地赢取分数：

- 将两组数据从小到大排序；
- 对于当前未被安排过的最强的一匹敌方马A[i]:
- 如果己方最弱的马B[j]能胜过它, 则让这匹较弱的马上阵对抗较强的对手;
- 否则就用自己最好的马来对付对方这一轮派出的马;

这种做法基于这样一个事实：当面对一个更强的竞争对象时，应该优先考虑牺牲掉那些无论如何都会输掉的比赛资源去换取其他可能获胜的机会；而对于明显占优的情况，则应当毫不犹豫地争取胜利[^3]。

#### Python代码实现

def tianji_race(tianji_horses, king_horses):
    # 排序两个列表
    tianji_horses.sort()
    king_horses.sort()

    score = 0
    i = j = 0
    
    while i < len(king_horses) and j < len(tianji_horses):
        if tianji_horses[j] > king_horses[i]:
            score += 1
            i += 1
        j += 1
        
    return score


if __name__ == "__main__":
    tianji = [90, 80, 70]
    king = [95, 85, 75]

    result = tianji_race(tianji, king)

    print(f"Tian Ji wins {result} races.")

上述程序模拟了田忌与国王之间赛马的过程，并计算出了最终得分情况。在这个例子中，田忌可以通过合理的调度战胜一次国王的马匹[^2]。