田忌赛马是一个很经典的故事，即田忌和齐威王赛马，虽然同等级的马不如齐威王的，但通过“上对中，中对下，下对上”这样的策略3局2胜。

问题限制在3匹马这样的范围很容易脑补出可行方案，但如果规模更大的问题呢，如何去编程解决？以一道leetcode上的田忌赛马类似题870. 优势洗牌来进行说明。把nums1当作田忌所有马的能力值，nums2当作齐威王所有马的能力值，返回一个田忌所有马的出战顺序使得对齐威王的优势最大。

贪心法

可以这样思考，我们先对田忌手里的马按能力从小到大排序，然后每次取能力最小的马，如果能战胜齐威王的任何一匹马，那就派它和这匹能战胜的马战斗并拿下一分，反之，则和齐威王目前最厉害的马战斗，为之后的中马战下马争取机会。

为了快速找到能战胜的马，齐威王的马也需要排序，从小到大排序如果目前能力最小的马都战胜不了那就和目前最厉害的马战斗。这样我们可以想到用排序和双指针，一个指针指向当前最弱的马，另一个指向最强的马。

又因为需要返回带顺序的排列结果，所以实际不能对nums2排序，这样会丢失原来的出战顺序。我们可以对下标排序，用lambda表达式可以很好地做到用元素值对下标排序。

最后，按照下标数组指示的顺序填入结果数组即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 田忌赛马，用田忌最低等的马比齐威王最低等的马
        # 如果能比过则田忌拿下一分，反之则直接用这匹马比齐威王最厉害的马
        # 如此操作将问题转化为n-1规模
        n = len(nums1)
        nums1.sort()
        # nums2要保持相对顺序，得对idx排序
        idxs = [i for i in range(n)]
        idxs.sort(key=lambda idx: nums2[idx])

        ans = [0 for i in range(n)]
        left, right = 0, n-1
        # 开始比较
        for x in nums1:
            if x > nums2[idxs[left]]:
                ans[idxs[left]] = x
                left += 1
            else:
                # 比最强的马
                ans[idxs[right]] = x
                right -= 1
        
        return ans

更多的思考

如果田忌一开始的马并不是满编，而是齐威王有n匹马而且出战顺序已知，而田忌只有m匹马(m<=n)，但他可以用k元，买到能力值为k的一匹马(k>=1)，这样田忌怎么设计才能以最少的钱战胜齐威王，如果不能战胜则返回-1。

这题感觉还是不能直接复刻贪心法的思路，因为一开始马都不全，马应该用二分查找找能力接近但能战胜的，这样能力浪费应该最少。但如果没有能力接近而且能战胜的，只有平局的又不知道咋弄，这些马似乎得之后统筹。后面输的炮灰马可以买能力值为1的，但平局和胜利实际只有1块钱的差值，所以这些原来可用的平局马似乎又还有一定作用，默认把它们当炮灰又可能不是最优，这个不知道咋处理了。

如果安排完原来的马匹没有平局马，后面的安排可以遍历i胜j负k平的解空间，可用很容易知道i局胜的应该在赢当前齐威王马里面最弱的i匹马，需要sum(nums2_p[:i+1])+len(nums2_p[:i+1])元钱买马才能战胜，因为每匹马都需要至少比齐威王马能力值高1。之后是平局空间，平局空间需要和齐威王能力值相当，因此也要尽可能比弱的。最后是负空间，负空间需要炮灰马，只需要能力值为1的马就行，要输j局只需要j块钱。

这里有个缩小解空间的办法，假设手里的马战成m1胜m2负m3平，则遍历时i+m1最多遍历到min(n//2+1, n-m1-m2-m3)，因为赢一半最后怎么都赢了。然后就是j应该最多遍历到i+m1-1，不可能输超过这个数。可以知道输是成本最低的买法，所以一定会尽可能输完i+m1-1局，最后k局平局是通过i,j确定后唯一确定的，这里就省去了j和k的两次循环。实际这一步只有O(n-m)的复杂度？

如果无法确定要战平还是战输，这里也可以进行分叉，m1胜是一定的，m2和m3可能有多个取值，然后从多个取值构成的解空间进行遍历得到最后的解。但复杂度应该是堪忧，尤其是故意构造多个平局的马，解空间里不停遍历每一步也需要O(n-m)的复杂度，最坏是剩下的马都有战平可能，即存在n-m1+1种排列，最后可能整个算法是O(n-m1+1)*O(n-m)=O(n^2)的复杂度。

因为这道题在leetcode上没找到原题，当时也没做出来，不知道这样能不能过，现在是这样想的。