田忌大师赛马故事背后的两个指标的算法——孙膑

田忌和齐王赛马，他的马分为高、中、低。如果相同等级的马匹在竞争中对决，田忌无法击败齐王。但田忌遇到了孙膑，孙膑教他用马对齐王的低马，然后是马对齐王的中马，最后是马对齐王的低马。结果，田忌在三场比赛中赢了两场。 。

当然，这段历史也很有趣。嘲笑齐王接受建议的自恋者邹忌和田吉是同一时代的人，两人后来和好了。但这是个玩笑，所以我们就到此为止。

当我研究田忌的赛马论文时，我想，如果不是三匹赛马，而是百匹赛马，孙膑还能合理安排比赛顺序，赢得比赛吗？齐王？

我当时找不到好主意。我只是觉得，这里真正的问题是我在利用自己，让对方尽可能地受苦。总之，如果你能打败他，就和他战斗；如果你能打败他，就和他战斗；如果打不倒他，就用自己的垃圾和对方的精英交换。

不过，我从来没有详细应用过这个想法，直到最近在理扣上看到第870题“优势洗牌”，我立刻意识到这是田忌赛马题的改进版：

插入两个将相等长度的nums1和nums2放入数组中。请重新排列nums1中的项目位置，并使其nums1固定“优势”。

如果 nums1[i] > nums2[i]，则 nums1 与 nums2 中的相反[i] 有“优点”。增加增益意味着我们可以尽可能地重新排列nums1，，使得nums[i] > nums2[i]。

算法签名如下：

int[] advantageCount(int[] nums1, int[] nums2);

例如输入：

nums1 = [12,24,8,32]
nums2 = [13,115]

您的算法应返回[24,32,8,12]，因为如果nums1这样排列的话，三个元素都有“优势”。 ？你的真正技能

。

如果仔细看的话，这个问题的答案还是很混乱的。什么时候应该停止反抗、停止杀人，什么时候应该强硬？应该有一种算法策略来最大化“优势”。

提及某人必须是万不得已且适当的，否则旁边的田忌就会开始骂你的谈话。只有当田忌的优质马匹敌不过齐王的马匹时，才会将劣质马匹换成齐王的马匹。

对于比较困难的问题，可以尝试考虑具体情况。

你认为谁应该带领齐王的马跑得最快？它必须是田忌跑得最快的马，也就是我们所说的第一匹马。简称1。

如果不比田忌的头号选手好的话，其他的马肯定都给了。当然，在这种情况下，田忌的低马应该用来释放杀戮，减少个人损失，并节省力量，增加下一场比赛的胜率。

但是如果你能和No.玩家竞争的话。齐王的1号球员1 田忌，跟齐王一样强。不管怎样，田忌都能打败它。

你可能会说，在这种情况下，也许是 2 号球员。 2 田忌可以击败排名第一的球员。齐王也是1吗？如果可以的话，让二号球员去和齐王的一号球员竞争不是更经济吗？

就像，如果你可以用 60 度来应付，为什么还要费心去 61 度呢？每获得一分，您就会失去一分。停在60点是最贵的。

这种节省策略很方便，但不是必需的。这也是这个问题有趣的地方。这需要集思广益：

让我们暂时称呼玩家为No。田忌的 T1 中的 1 号，以及玩家的 1 号。 2 称为Q1。

如果T2能赢Q1那就尽力保护你的力量，让它战斗❀T2Q1 ，放入 T1 你在做什么？

当然担心齐王还有比T2更强的马，所以就让T1来对付。

但是仔细看的话，现在T2已经可以赢Q1、

Q1、Q1、 会比其他马匹更强.T2？

因此，无需保存。我们制定的最终策略是：

根据战争中的成功对齐王和田忌的战马进行排名，并按顺序进行比较。如果田忌的马能赢，我们就比赛吧。如果不胜，就换下底马，给它头，以保住势力。

上述概念的代码逻辑如下：

int n = nums1.length;

sort(nums1); // 田忌的马
sort(nums2); // 齐王的马

// 从最快的马开始比
for (int i = n - 1; i >= 0; i--) {
    if (nums1[i] > nums2[i]) {
        // 比得过，跟他比
    } else {
        // 比不过，换个垫底的来送人头
    }
}

根据这个概念，我们需要追踪两个数组，但是nums2中元素的顺序是无法改变的，因为顺序计算结果的大小取决于nums2 的顺序，所以nums2无法直接排序，需要使用其他数据结构来帮助。

同时，最终的解决方案采用了上一篇文章《两指标能力总结》中总结的两指标的算法模型来处理“头部交接”的情况：

int[] advantageCount(int[] nums1, int[] nums2) {
    int n = nums1.length;
    // 给 nums2 降序排序
    PriorityQueue<int[]> maxpq = new PriorityQueue<>(
        (int[] pair1, int[] pair2) -> { 
            return pair2[1] - pair1[1];
        }
    );
    for (int i = 0; i < n; i++) {
        maxpq.offer(new int[]{i, nums2[i]});
    }
    // 给 nums1 升序排序
    Arrays.sort(nums1);

    // nums1[left] 是最小值，nums1[right] 是最大值
    int left = 0, right = n - 1;
    int[] res = new int[n];

    while (!maxpq.isEmpty()) {
        int[] pair = maxpq.poll();
        // maxval 是 nums2 中的最大值，i 是对应索引
        int i = pair[0], maxval = pair[1];
        if (maxval < nums1[right]) {
            // 如果 nums1[right] 能胜过 maxval，那就自己上
            res[i] = nums1[right];
            right--;
        } else {
            // 否则用最小值混一下，养精蓄锐
            res[i] = nums1[left];
            left++;
        }
    }
    return res;
}

复杂度的时间。算法很容易分析，就是二进制文档，分类难度是O(nlogn)。

至此，这个田忌赛马问题就解决了。代码实现使用两种索引技术。从最快的马开始，如果可以比较，就比较。如果无法比较，则给出。这样就可以比较马匹的数量了。找到最佳的游戏策略。

作者：labuladong