拼题a7-3 贪心算法（田忌赛马）

### 贪心算法在田忌赛马中的应用

#### 实现方法

贪心算法通过局部最优策略来尝试获得全局最优解。对于田忌赛马问题，核心思想是在每一轮比赛中尽可能使当前可选的最强马匹获胜或避免失败。

具体来说：

- 对手和己方的马按照战斗力降序排列。
- 尝试用最弱的马去对抗对方无法赢得比赛的最强马（即摆烂），从而保存实力用于其他场次；如果可以赢，则派出能够战胜该对手最小代价的马。
- 如果上述两种情况都不成立，则直接放弃本轮比赛[^1]。

这种方法确保了整体上最大化胜利次数的同时也考虑到了资源的有效利用。

#### Python 示例代码

以下是基于此逻辑编写的Python版本解决方案:

from typing import List

def advantageCount(nums1: List[int], nums2: List[int]) -> List[int]:
    sorted_nums1 = sorted(nums1)
    result = []
    
    for num in nums2:
        found = False
        
        for i, val in enumerate(sorted_nums1):
            if val > num:
                result.append(val)
                del sorted_nums1[i]
                found = True
                break
                
        if not found and len(sorted_nums1) != 0:
            temp = min(sorted_nums1)
            result.append(temp)
            sorted_nums1.remove(temp)

    while len(result)<len(nums2):  
        result.extend(sorted_nums1[:])
        
    return result[:len(nums2)]

print(advantageCount([8,12,24,32,6],[998,13,32,25,11])) # 输出应体现贪心原则下的匹配方案

这段程序实现了针对给定两组数据`nums1`(代表自己拥有的马的速度列表)`nums2`(敌人的马)，返回一个新的数组表示如何安排自己的马来应对敌人以达到最大胜率的结果集[^3]。