参阅基础

简介

田忌赛马的故事大家应该都听说过：

田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着比赛，田忌赢不了齐王。但是田忌遇到了孙膑，孙膑就教他用自己的下等马对齐王的上等马，再用自己的上等马对齐王的中等马，最后用自己的中等马对齐王的下等马，结果三局两胜，田忌赢了。

这里面的核心思路就是用自己的老弱残兵与对方的精锐互换。

但什么时候应该放弃抵抗？什么时候应该硬碰硬？是一个值得思考的问题。

谁应该去应对齐王最快的马？肯定是田忌最快的那匹马。如果田忌最快的马比不过齐王最快的马，那其马也肯定不是对手，这种情况应该用田忌垫底的马去与齐王互换。

如果田忌最快的马比得过齐王的最快的马，那就和齐王硬碰硬。

但这种情况下，说不定田忌第二快的马也能比得过齐王最快的马？如果可以的话，让田忌第二快的马去比赛，是不是更节约？

实际上，这种节约没问题，但是没有必要。节约的目的是保留田忌最快的马，以对付强大的对手。但假如田忌第二快的马就已经能比得过齐王最快的马，田忌最快的马还需要保留着对付谁？所以，没必要节约。

最后得出的策略就是：

将齐王和田忌的马按照战斗力排序，然后按照排名一一对比。如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的马来比赛，保存实力。

这里其实蕴藏了贪心算法的思想。

相关题目

leetcode 870 优势洗牌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var advantageCount = function(nums1, nums2) {
    let num1 = nums1.sort((a,b)=> a - b)
    let num2Indx = new Array(nums2.length).fill(0).map((_,index)=>index).sort((a,b)=>nums2[b]-nums2[a])

    let left = 0,right = num1.length - 1
    const result = new Array(num1.length).fill(-1)
    for(let idx of num2Indx){
        if(nums2[idx] >= num1[right]){
            result[idx] = num1[left++]
        }else{
            result[idx] = num1[right--]
        }
    }
    return result
};